TL;DR
This paper proves that several fundamental graph problems, including Edge Clique Cover and various forms of Multicut and k-Way Cut, do not admit polynomial-time preprocessing algorithms (kernels) unless a major collapse in computational complexity occurs. This establishes theoretical limits on how efficiently these problems can be simplified before being solved.
What Problem Does This Paper Address?
In parameterized complexity, a key goal is to find efficient algorithms for computationally hard problems by focusing on a specific "parameter" of the input. A crucial part of this is "kernelization," which involves a polynomial-time preprocessing step that reduces the input size to a function of the parameter. The existence of a "polynomial kernel" means this preprocessing step can shrink the input size to be polynomial in the parameter, making subsequent exact algorithms feasible.
However, for many important problems, it's unknown if polynomial kernels exist. This paper addresses this by proving lower bounds on kernelization for several problems, showing that polynomial kernels are unlikely to exist unless very strong complexity assumptions are violated. This is important because it tells us when we should stop searching for polynomial kernels and focus on other algorithmic approaches.
Methods
The core technique used in this paper is cross-composition, a powerful framework for proving kernelization lower bounds. The idea is to show that if a problem did have a polynomial kernel, it would imply a collapse in the polynomial hierarchy (a major complexity class). This is achieved by constructing a "composition" algorithm:
- Start with a known NP-complete problem (L): This is the "source" problem.
- Construct a "cross-composition" algorithm: This algorithm takes multiple instances of L and combines them into a single instance of a target parameterized problem (Q). The key is that the combined instance is a "YES" instance for Q if and only if at least one of the original instances of L was a "YES" instance.
- Show that if Q has a polynomial kernel: Combining the cross-composition with a hypothetical polynomial kernel for Q would allow for an "OR-distillation" of L. This means we could compress multiple instances of L into a much smaller instance that still encodes the "OR" of the original instances.
- Implication: The existence of such an OR-distillation is known to imply that NP is contained in coNP/poly, which in turn collapses the polynomial hierarchy. Therefore, if we assume the polynomial hierarchy does not collapse (a standard assumption in complexity theory), then Q cannot have a polynomial kernel.
The paper applies this framework by carefully designing specific NP-complete problems and constructing intricate gadgets to build the cross-composition for each target problem. They also introduce and utilize the concept of "AND-cross-composition" for some problems, which is related to the "AND-conjecture" in kernelization theory.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity and does not involve empirical evaluation on datasets.
Key Insights and Ideas
- Theoretical Limits on Preprocessing: The paper establishes fundamental limits on how much we can simplify certain graph problems before solving them, even with a polynomial parameter. This is crucial for understanding the inherent complexity of these problems.
- Cross-Composition as a Powerful Tool: The paper demonstrates the effectiveness of the cross-composition technique for proving kernelization lower bounds, extending its application to a range of important graph problems.
- Edge Clique Cover's Unique Position: The paper highlights that Edge Clique Cover is one of the first natural parameterized problems shown to admit both AND- and OR-composition algorithms, making its kernelization status particularly interesting and tied to the AND-conjecture.
- Interplay between Graph Separation Problems: The results for Multicut and k-Way Cut show that these related problems also likely lack polynomial kernels, complementing recent algorithmic advancements in the area.
- Gadget Design: The paper showcases sophisticated gadget constructions within the cross-composition framework, which are often key to proving such lower bounds.
Key Results
The paper proves that the following parameterized problems do not admit polynomial kernelizations, unless NP ⊆ coNP/poly (which implies a collapse of the polynomial hierarchy):
- EDGE CLIQUE COVER, parameterized by the number of cliques.
- DIRECTED EDGE/VERTEX MULTIWAY CUT, parameterized by the size of the cutset, even for two terminals.
- EDGE/VERTEX MULTICUT, parameterized by the size of the cutset.
- k-WAY CUT, parameterized by the size of the cutset.
Limitations and Future Work
- Complexity Assumption: The results are conditional on the polynomial hierarchy not collapsing. If NP ⊆ coNP/poly were true, then polynomial kernels could exist for these problems.
- Open Problems: The paper explicitly mentions several open questions:
- Is the double-exponential dependency in the fastest fixed-parameter algorithm for EDGE CLIQUE COVER necessary?
- The kernelization hardness for DIRECTED MULTIWAY CUT with deletable terminals and for MULTICUT in directed acyclic graphs remains open.
- The paper asks if MULTICUT parameterized by both cutset size and the number of terminal pairs is similarly hard to kernelize.
- Generalization: The authors suggest that the techniques used, particularly the gadget designs, might inspire future work on proving lower bounds for other problems.
Summary updated