Provable Data Reduction through Polynomial Kernelization

320 concepts182 papers2 proposals

When facing NP-hard problems, practitioners routinely turn to preprocessing heuristics to shrink the input size before running an expensive solver. While these heuristics often work well in practice, they typically lack theoretical guarantees. Kernelization bridges this gap by providing a mathematically rigorous framework for preprocessing, ensuring that a large instance can be compressed into a smaller, equivalent core with a provable upper bound on its size.

The Core Intuition: Parameterized Compression

In classical complexity, preprocessing cannot guarantee a size reduction for NP-hard problems unless P = NP. Kernelization bypasses this barrier by using the lens of parameterized complexity. Instead of measuring an instance solely by its total input size $n$, we identify a parameter $k$ that captures a specific structural property or the target solution size.

A kernelization algorithm is a polynomial-time procedure that transforms an initial instance $(I, k)$ into an equivalent instance $(I', k')$—known as the kernel—such that the size of $I'$ and $k'$ are bounded entirely by a function of $k$, completely independent of $n$. As noted by Pinar Heggernes in Foreword: Special Issue on IPEC 2014, this process isolates the computationally intractable components of a problem into a compressed representation, allowing downstream exact or heuristic solvers to process the core difficulty efficiently.

Why It Works: The Power of Local Reduction Rules

The mechanism driving kernelization is the systematic application of reduction rules. These rules exploit local constraints to make global decisions, pruning away parts of the instance that are either trivially included in a solution or entirely irrelevant.

To see why this works, consider a graph layout or modification problem. If a specific vertex has a property that violates the target structure too severely, any valid solution must modify or include it. Conversely, if a component is completely isolated, it can be safely discarded. By repeatedly applying these polynomial-time rules until no further reductions are possible, the instance shrinks to its irreducible core.

Yeo et al. demonstrate this intuition in Fixed-Parameter Complexity of Minimum Profile Problems. By designing rules that prune and merge redundant structural layouts, the authors show that a graph can be compressed down to a kernel of linear size ($12k + 6$ vertices), meaning the remaining search space depends strictly on the distance from a guaranteed lower bound rather than the size of the original network.

Structural Modulators

A highly effective strategy for achieving a polynomial-sized kernel is isolating a modulator. A modulator is a small set of elements whose removal transforms the complex, intractable part of an instance into a well-behaved, easily solvable structure (such as a collection of disjoint trees or paths).

Once a modulator is identified, the algorithm can bound the size of the remaining "easy" parts of the instance relative to the modulator's size. In Unit interval vertex deletion: Fewer vertices are relevant, Ke et al. employ a constant-approximation algorithm to find a modulator that is linear in size with respect to the parameter $k$. By proving that only a small, bounded number of vertices outside this modulator can meaningfully interact with it, the authors systematically prune the rest of the graph, successfully shrinking the kernel size from a high-degree polynomial down to a manageable $O(k^4)$ vertices.

Combinatorial Pruning via the Sunflower Lemma

For logic-based or set-theoretic problems, kernelization often relies on deep combinatorial properties to bound instance sizes. A prime example is the Sunflower Lemma. A "sunflower" is a collection of sets that all share the exact same common intersection (the core).

If an instance contains a massive number of constraints that form a sunflower, many of them become redundant. Because any valid assignment can only satisfy or violate the core or a limited number of "petals," the excess petals can be stripped away without altering the solvability of the problem. In Solving Quantified Boolean Formulas with Few Existential Variables, Eriksson et al. utilize this exact combinatorial mechanism. By identifying and eliminating redundant clauses that form sunflowers, they ensure that the final formula's size depends strictly on fixed parameters like clause length and the number of existential variables, rather than the total input length.

Beyond Exact Equivalence: Lossy and Solution-Preserving Kernels

Traditional kernelization is strictly "existential"—it guarantees that the kernel has a solution if and only if the original instance does. However, modern algorithmic challenges require more nuanced variations of this paradigm.

Lossy and Approximate Kernelization

For many optimization problems, finding an exact polynomial kernel is mathematically impossible. To overcome this, researchers relax the exactness requirement by allowing a bounded amount of error. Pasin Manurangsi demonstrates this approach in Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back and A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. By scaling and rounding weights, the author compresses large optimization instances into polynomial-sized approximate kernels. This ensures that any near-optimal solution found on the compressed kernel can be lifted back to a near-optimal solution for the original instance within a provable error tolerance.

Solution-Preserving and Loss-Less Kernelization

In fields like Constraint Programming, simply knowing whether a solution exists is insufficient; solvers must preserve all valid variable assignments to perform constraint propagation and domain pruning. To address this, Carbonnel et al. introduce frameworks for loss-less kernelization in On the Kernelization of Global Constraints. Instead of merely preserving satisfiability, these reduction rules maintain all valid assignments (supports), allowing constraint solvers to execute complete propagation on a highly compressed representation of an NP-hard constraint.

The Hard Limits of Preprocessing

It is vital to recognize that kernelization is not a silver bullet. Even if a problem is Fixed-Parameter Tractable (FPT)—meaning it can be solved efficiently when $k$ is small—it may still resist polynomial compression.

In Limits of Preprocessing, Stefan Szeider establishes the fundamental theoretical boundaries of this field. The author proves that for several core AI tasks, including general Constraint Satisfaction Problems (CSP) and Bayesian inference, reducing large instances to polynomial-sized kernels is mathematically impossible unless the polynomial hierarchy collapses. This boundary provides crucial guidance, telling researchers exactly where polynomial-time data reduction is viable and where algorithms must contend with exponential kernel sizes.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_kernelization_2c177903,
  title = {kernelization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/kernelization/rdr_2c177903e62a49b29434b978332d5452},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_kernelization_2c177903_v1,
  title = {kernelization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/kernelization/rdr_2c177903e62a49b29434b978332d5452/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake