Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
Bart M. P. Jansen · Lecture notes in computer science · 2020
Abstract On the occasion of Hans Bodlaender’s 60th birthday, I give a personal account of our history and work together on the technique of cross-composition for kernelization lower bounds. I present several simple new proofs for polynomial kernelization lower bounds using cross-composition, interlaced with personal anecdotes about my time as Hans’ PhD student at Utrecht University. Concretely, I will prove that Vertex Cover , Feedback Vertex Set , and the H -Factor problem for every graph H that has a connected component of at least three vertices, do not admit kernels of $$\mathcal {O}(n^{2-\varepsilon })$$ O ( n 2 - ε ) bits when parameterized by the number of vertices n for any $$\varepsilon > 0$$ ε > 0 , unless $$\mathsf {NP \subseteq coNP/poly}$$ NP ⊆ coNP / poly . These lower bounds are obtained by elementary gadget constructions, in particular avoiding the use of the Packing Lemma by Dell and van Melkebeek.