Analysis of Data Reduction: Transformations give evidence for non-existence of polynomial kernels
Hans L. Bodlaender, Anders Yeo · 2008
In this paper, we introduce a new technique to give evidence for combinatorial problems that they cannot be preprocessed in polynomial time such that resulting instances always have a size bounded by a polynomial in a specified parameter (or, in short: do not have a polynomial kernel); these results are assuming the validity of certain complexity theoretic assumptions. We build upon a framework by Bodlaender et al. [6], and add a notion of transformation to this framework. Using these transformations, we show that Disjoint Cycles, and Disjoint Paths do not have polynomial kernels, unless the or-distillation conjecture does not hold, which would imply by a result of Fortnow and Santhanam [12] that NP ⊆ coNP/poly, and we show that Hamiltonian Circuit parameterized by treewidth does not have a polynomial kernel, unless the and-distillation conjecture does not hold. We also show that the problem to determine if there are k edge disjoint cycles has a polynomial kernel.