Cross-Composition: A New Technique for Kernelization Lower Bounds

Abstract

We introduce a new technique for proving kernelization lower bounds, called cross-composition. A classical problem L cross-composes into a parameterized problem Q if an instance of Q with polynomially bounded parameter value can express the logical 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) we show that if an NP-complete problem cross-composes into a parameterized problem Q then Q does not admit a polynomial kernel unless the polynomial hierarchy collapses. Our technique generalizes and strengthens the recent techniques of using OR-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., Chromatic Number, Clique, and Weighted Feedback Vertex Set 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. We have similar lower bounds for Feedback Vertex Set.

Updated information based on final version submitted to STACS 2011

Cited by in corpus (20)

• Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter
• Data Reduction for Graph Coloring Problems
• Simultaneously Satisfying Linear Equations Over ${\mathbb{F}}_2$: MaxLin2 and Max-$r$-Lin2 Parameterized Above Average
• On the Parameterized Complexity of Computing Balanced Partitions in Graphs
• Hierarchies of Inefficient Kernelizability
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Representative sets and irrelevant vertices: New tools for kernelization
• Kernelization Lower Bounds By Cross-Composition
• Lossy Kernelization
• Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
• Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?
• Clique cover and graph separation: New incompressibility results
• Linear vertex-kernels for several dense ranking r-CSPs
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Explicit linear kernels via dynamic programming
• Confronting Intractability via Parameters
• Fixing improper colorings of graphs
• On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem
• Conflict Packing: an unifying technique to obtain polynomial kernels for editing problems on dense instances
• (Non-)existence of Polynomial Kernels for the Test Cover Problem