Source-linked AI summary
Kernelization Lower Bounds By Cross-Composition
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
TL;DR
The paper addresses how to prove that fixed-parameter tractable problems lack polynomial kernels. It introduces cross-composition, which combines classical NP-hard instances into parameterized instances with polynomially bounded parameters, and derives lower bounds for several graph problems under vertex-cover parameterization.
Problem
Kernelization provides formal data reduction, but techniques were needed to establish when fixed-parameter tractable problems do not admit polynomial kernels.
Method
The paper introduces cross-composition, combining the OR or AND of classical NP-hard instances into a parameterized target instance with polynomially bounded parameter.
Results
Cross-composition yields kernelization lower bounds for Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal parameterized by vertex cover.
Takeaways & Limitations
The framework strengthens earlier composition and polynomial-parameter-transformation methods and supports applications to structural parameterizations.
Takeaways & Limitations
The structural-parameterization formulations supply a vertex cover witness in the input to permit efficient recognition of well-formed instances.
Abstract
from arXiv · showhide
We introduce the cross-composition framework for proving kernelization lower bounds. A classical problem L AND/OR-cross-composes into a parameterized problem Q if it is possible to efficiently construct an instance of Q with polynomially bounded parameter value that expresses the logical AND or OR of a sequence of instances of L. Building on work by Bodlaender et al. (ICALP 2008) and using a result by Fortnow and Santhanam (STOC 2008) with a refinement by Dell and van Melkebeek (STOC 2010), we show that if an NP-hard problem OR-cross-composes into a parameterized problem Q then Q does not admit a polynomial kernel unless NP \subseteq coNP/poly and the polynomial hierarchy collapses. Similarly, an AND-cross-composition for Q rules out polynomial kernels for Q under Bodlaender et al.'s AND-distillation conjecture. Our technique generalizes and strengthens the recent techniques of using composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (non-standard) parameterizations, e.g., Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. After learning of our results, several teams of authors have successfully applied the cross-composition framework to different parameterized problems. For completeness, our presentation of the framework includes several extensions based on this follow-up work. For example, we show how a relaxed version of OR-cross-compositions may be used to give lower bounds on the degree of the polynomial in the kernel size.
1 Introduction
The paper introduces cross-composition as a framework for proving kernelization lower bounds and applies it to structural parameterizations of fundamental graph problems. It strengthens earlier composition and polynomial-parameter-transformation techniques while incorporating later extensions.
- Motivation: Kernelization formalizes data reduction and permits rigorous analysis of when preprocessing can or cannot yield polynomial-size instances.It originated as a technique for obtaining fixed-parameter tractable algorithms and developed into an independent research topic.
- Cross-composition: Cross-composition combines instances of a classical NP-hard problem into one parameterized instance whose parameter is polynomially bounded in the largest input size.The source and target problems may differ, unlike ordinary compositions of parameterized instances.
- Relation to prior techniques: The framework generalizes and strengthens composition algorithms and polynomial parameter transformations by placing both lower-bound techniques in a common perspective.It also allows the source and target problems of a composition to differ.
- Applications: Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal have no polynomial kernels parameterized by vertex cover unless the polynomial hierarchy collapses.These problems remain fixed-parameter tractable for this structural parameterization.
- Extensions: Later extensions include an and-cross-composition variant and a relaxed or-cross-composition for proving polynomial lower bounds on kernel size.The paper incorporates improvements and follow-up developments after its extended abstract.
2 A review of kernelization lower bound techniques
This section reviews kernelizations, compressions, compositions, distillations, and the complexity-theoretic results that turn composition procedures into kernelization lower bounds.
- Kernelizations and compressions: A kernelization maps an instance to an equivalent instance of the same parameterized problem whose encoding size and parameter are bounded by a computable function of the original parameter.Polynomial kernels are the special case where the bounding function is polynomial.
- Kernelizations and compressions: A compression maps a parameterized instance to a short string in a language, preserving yes/no equivalence; polynomial compression requires polynomial output length.Compressions relax generalized kernelizations, which in turn relax kernelizations.
- Compositions and distillations: Weak distillations combine classical instances into a polynomially bounded output while preserving an OR or AND of their answers.The framework distinguishes these from compositions because distillations bound overall output size rather than an output parameter.
- Compositions and distillations: An or-composition combines parameterized instances sharing one parameter into an instance whose polynomially bounded parameter encodes whether at least one input is yes.An and-composition instead requires all input instances to be yes.
- Lower-bound consequences: If an NP-hard parameterized problem has a polynomial kernel or compression and an or-composition, then satisfiability has a weak or-distillation.An and-composition yields an and-distillation instead.
- Lower-bound consequences: Fortnow and Santhanam imply that a weak or-distillation for satisfiability places NP in coNP/poly and collapses the polynomial-time hierarchy to its third level.The and-distillation counterpart relies on the stated conjecture in this review.
- Lower-bound consequences: The complementary witness lemma gives a coNP/poly consequence from a low-cost oracle communication protocol with a co-nondeterministic first player.Its communication cost is O(t(s) log t(s)) for tuples of t(s) strings of length at most s.
- Lower-bound consequences: Polynomial parameter transformations transfer polynomial kernelizations, compressions, and generalized kernelizations from a target problem back to the source problem.This enables lower bounds for problems lacking a direct composition.
3 Cross-composition
Cross-composition combines equivalent instances of a classical language into one parameterized instance whose answer represents their logical OR or AND, while keeping the parameter polynomially bounded. Combined with polynomial compression, this framework yields kernelization lower bounds and, for relaxed OR compositions, lower bounds on kernel-size degree.
- Basic framework: Cross-composition algorithms group inputs under a polynomial equivalence relation before constructing a parameterized instance.The relation is efficiently decidable and partitions any finite input set into polynomially many classes.
- Basic framework: An OR-cross-composition outputs a yes-instance exactly when at least one grouped input is yes, whereas an AND-cross-composition requires all grouped inputs to be yes.Both variants require the output parameter to be polynomially bounded in the largest input size and log t.
- Basic framework: Polynomial compression combined with AND- or OR-cross-composition yields weak AND- or OR-distillation for the source language.The AND case is stated explicitly for arbitrary target language L′, and the analogous OR result also holds.
- Lower bounds: NP-hard AND-cross-compositions rule out polynomial kernels or compressions unless the AND-distillation conjecture fails.This consequence applies to generalized polynomial kernelizations as well.
- Lower bounds: NP-hard OR-cross-compositions rule out polynomial kernels or compressions unless the OR-distillation conjecture fails and NP ⊆ coNP/poly.Fortnow and Santhanam’s result supplies the NP ⊆ coNP/poly consequence under the stated assumption.
- Bounded-cost extensions: OR-cross-compositions with subpolynomial dependence f(t) = t^o(1) exclude polynomial compression, while bounded-cost compositions can rule out compression size O(k^(d−ε)).The bounded-cost theorem states that an OR-cross-composition of cost t^(1/d+o(1)) together with compression size O(k^(d−ε)) implies L ∈ coNP/poly.
4 Our lower bounds
The section applies cross-composition to obtain kernelization lower bounds for fundamental graph problems under structural parameterizations. These problems remain fixed-parameter tractable in several cases, but do not admit polynomial kernels unless NP ⊆ coNP/poly.
- Overview: Cross-composition yields kernelization lower bounds for Clique, Chromatic Number, Feedback Vertex Set, and Odd Cycle Transversal under structural parameterizations.The presented constructions use OR-cross-compositions, and the lower bounds also apply to generalized kernelizations.
- Clique and Vertex Cover: Clique parameterized by Vertex Cover does not admit a polynomial kernel unless NP ⊆ coNP/poly.The proof cross-composes Clique instances into one instance whose parameter is polynomially bounded.
- Clique and Vertex Cover: The construction also implies that Vertex Cover and Independent Set parameterized by clique deletion set lack polynomial kernels unless NP ⊆ coNP/poly.The stated corollary applies to every graph class containing all cliques.
- Chromatic Number: Chromatic Number parameterized by Vertex Cover does not admit a polynomial kernel unless NP ⊆ coNP/poly.The cross-composition uses restricted 3-Coloring instances and produces an output with ℓ′ = log t + 4.
- Chromatic Number: For every fixed q, q-Coloring parameterized by Vertex Cover has a kernel with O(kq) vertices, so the unrestricted-color lower bound does not extend unchanged to fixed q.The result shows that q must occur in the degree of the polynomial for such kernels.
- Feedback Vertex Set and Odd Cycle Transversal: Feedback Vertex Set and Odd Cycle Transversal lack polynomial kernels parameterized by clique deletion set, while their weighted variants lack polynomial kernels parameterized by Vertex Cover.The unweighted result uses a polynomial parameter transformation, whereas the weighted result uses cross-composition from Vertex Cover.
5 Conclusions
The paper concludes that cross-composition is a fruitful framework for kernelization lower bounds, with applications to structural parameterizations and extensions developed in follow-up work.
- Cross-composition yields kernelization lower bounds for several graph problems under structural parameterizations.
- Many cross-compositions exploit input graphs whose vertex sets split into parts inducing pairwise isomorphic subgraphs across instances.
- Co-nondeterministic cross-compositions extend the framework and can exclude polynomial kernels or compressions under subpolynomial dependence on the number of inputs.