Clique cover and graph separation: New incompressibility results

Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström

Introduction

Can fundamental graph problems be efficiently compressed via preprocessing? This paper provides a definitive "no" for several classic problems. Using the framework of cross-composition, the authors demonstrate that problems like Edge Clique Cover and various Graph Cut problems do not admit polynomial kernels. This means they cannot be reduced to a size polynomial in their parameters without causing a major collapse in computational complexity theory.

The Problem: Preprocessing and Polynomial Kernels

In parameterized complexity, a common strategy for NP-hard problems is to use a "polynomial kernel." This is a preprocessing algorithm that takes an instance with a parameter $k$ and outputs an equivalent instance whose size is bounded by a polynomial function of $k$, independent of the original input size $n$.

For years, the existence of polynomial kernels for problems like Edge Clique Cover remained a major open question.

Formal definition of the Edge Clique Cover problem.

While these problems were known to be "Fixed-Parameter Tractable" (solvable in time $f(k) \cdot poly(n)$), the paper proves that a small, polynomial-sized "distilled" version likely does not exist.

Methodology: Cross-Composition

The authors employ cross-composition (and its variant, AND-cross-composition) to prove these lower bounds. The logic follows a proof-by-contradiction:

  1. Assumption: Assume a problem has a polynomial kernel.
  2. Composition: Show that multiple independent instances of an NP-complete problem can be "glued" into a single instance of the target problem where the parameter $k$ grows slowly.
  3. Distillation: A polynomial kernel would then compress this giant instance into a tiny one, effectively "distilling" the logical OR (or AND) of many instances.
  4. Collapse: Such distillation would imply $NP \subseteq coNP/poly$, leading to a collapse of the Polynomial Hierarchy—an event considered highly improbable.

Key Insights and Gadgetry

The core of the proof lies in sophisticated "gadgets" used to merge instances. A recurring theme is the Instance Selector gadget. In the Edge Clique Cover proof, the authors construct a framework where the "budget" of cliques is just enough to cover the "glue" and exactly one of the input instances, forcing the solver to "choose" which instance to satisfy.

A visualization of the complex gadget construction used to prove incompressibility for Edge Clique Cover.

The authors also show that Edge Clique Cover is both AND-compositional and OR-compositional, providing exceptionally strong evidence against the existence of a polynomial kernel.

Key Results

The paper establishes that, unless the polynomial hierarchy collapses, the following problems do not admit polynomial kernels:

  • Edge Clique Cover: Parameterized by the number of cliques $k$.
  • Directed Edge/Vertex Multiway Cut: Parameterized by the size of the cutset, even for just two terminals.
  • Edge/Vertex Multicut: Parameterized by the size of the cutset.
  • k-Way Cut: Parameterized by the size of the cutset.

Conclusion and Future Work

These results set a theoretical ceiling on the effectiveness of preprocessing for these problems. While a kernel of size $2^k$ (exponential) is known for Edge Clique Cover, these findings suggest that exponential size might be unavoidable.

Future research may focus on specific variants that might still admit polynomial kernels, such as Multicut in Directed Acyclic Graphs (DAGs) or Directed Multiway Cut with deletable terminals, which remain promising frontiers.

Summary updated

BibTeX
@inproceedings{cygan2012clique,
  author = {Marek Cygan and Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Magnus Wahlström},
  title = {{Clique cover and graph separation: New incompressibility results}},
  booktitle = {ICALP},
  year = {2012},
  doi = {10.1007/978-3-642-31594-7\_22},
}
Figure