A more versatile model for enumerative kernelization: a case study for Vertex Cover
Pith reviewed 2026-05-08 07:13 UTC · model grok-4.3
The pith
Polynomial-delay kernels provide a flexible model for enumerative kernelization that adapts decision kernels for Vertex Cover.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
PD kernels are more flexible than the polynomial-delay enumeration kernel model while preserving its core qualities, because they permit ignoring bad solutions in the kernel during enumeration of the original instance. A generic framework adapts any polynomial decision kernel for a vertex-subset problem into a PD kernel of identical size. For the problem of enumerating all vertex covers of size at most k, this framework yields polynomial PD kernels under the same parameterizations as the decision version, including a short lifting procedure when the parameter is feedback vertex number.
What carries the argument
The polynomial-delay (PD) kernel model together with the generic framework that turns decision kernels into PD kernels for vertex-subset problems by providing a polynomial-delay lifting procedure for good solutions.
If this is right
- PD kernels exist for Enum Vertex Cover when parameterized by the vertex deletion distance to any minor-closed graph class.
- A polynomial PD kernel exists for Enum Vertex Cover parameterized by solution size or feedback vertex number, with only a few lines needed for the lifting algorithm.
- The known polynomial kernel for vertex deletion distance to c-treedepth generalizes directly to the enumeration setting.
- The same adaptation framework applies to other vertex-subset enumeration problems that possess polynomial decision kernels.
Where Pith is reading between the lines
- The model could make enumeration kernelization feasible for problems that resisted the stricter previous definition.
- Simpler lifting procedures may appear for other parameterizations once the framework is applied.
- The distinction between good and bad solutions in the kernel may connect to approximation or sampling techniques in enumeration algorithms.
- The approach suggests that many existing FPT enumeration algorithms could be turned into kernels with modest additional work.
Load-bearing premise
There exists a polynomial-delay lifting procedure that can identify good solutions from the kernel and produce the corresponding original solutions without the bad solutions destroying the delay guarantee.
What would settle it
An instance of Enum Vertex Cover where every polynomial-size kernel requires super-polynomial delay to lift good solutions, or a vertex-subset problem that has a polynomial decision kernel but admits no such lifting procedure.
read the original abstract
Enumerative kernelization is a recent promising at the intersection of parameterized complexity and enumeration algorithms, with two proposed models. The first, known as enum-kernels and due to Creignou et al., was too permissive, leading to constant-sized kernels for every problem solvable with FPT-delay. To remedy this, Golovach et al. proposed the polynomial-delay enumeration kernelization model that, while addressing the shortcoming of the previous one, appears to be too strict, which we believe is a central reason for the slow development of the area. In this paper, we propose a new model for enumeration kernels, which we have called polynomial-delay (PD) kernels. It is more flexible than Golovach et al.'s kernels while still preserving their qualities; informally, it allows us to ignore ``bad'' solutions of the compressed instance when producing the solution set of the input instance, but still requires that the ``good'' solutions are lifted with polynomial-delay. After discussing the main properties of our model, we design a generic framework for vertex-subset problems to adapt decision kernels into PD kernels of the same size. We showcase our model's versatility and the framework's expressive power on the \textsc{Enum Vertex Cover} problem, where we want to list all vertex covers of size at most $k$ of a given graph. We generalize the kernelization dichotomy by Bougeret et al. about the existence of polynomial kernels for \textsc{Vertex Cover} parameterized by the vertex deletion distance to a minor-closed graph class, as well as by the solution size or feedback vertex number. The second one, in particular, is significantly simpler than the known kernel, requiring only a few lines for its lifting algorithm. Beyond our framework, we also show how to generalize to the enumeration setting the kernel of Bougeret et al. for the vertex-deletion distance to $c$-treedepth.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces polynomial-delay (PD) kernels as a new model for enumerative kernelization that relaxes Golovach et al.'s strict model by allowing kernels to contain 'bad' solutions (which are ignored during lifting) while requiring that 'good' solutions are lifted with polynomial delay. It gives a generic framework converting decision kernels for vertex-subset problems into PD kernels of identical size, then applies the framework to Enum Vertex Cover to generalize Bougeret et al.'s kernelization dichotomy for parameterization by deletion distance to a minor-closed class and by feedback vertex number (with a notably short lifting procedure for the latter), plus an extension to c-treedepth deletion distance.
Significance. If the lifting procedures are shown to preserve polynomial delay after filtering, the PD-kernel model and generic framework would meaningfully expand the applicability of enumerative kernelization beyond the restrictive Golovach model, while the simplified feedback-vertex-number kernel for Enum Vertex Cover constitutes a concrete technical improvement.
major comments (2)
- [§4] §4 (generic framework): The central claim that any decision kernel for a vertex-subset problem yields a PD kernel of the same size rests on a lifting procedure that, given a kernel solution, decides in polynomial time whether it is 'good' and produces the corresponding original solutions without the enumeration order being destroyed by bad solutions. The manuscript must explicitly prove that the goodness test and lifting map run in time independent of the number of bad solutions; otherwise the polynomial-delay guarantee does not follow from the decision-kernel delay bound.
- [§5] §5 (Enum Vertex Cover, feedback-vertex-number case): The claim that the lifting algorithm 'requires only a few lines' is load-bearing for the asserted simplicity advantage over prior kernels. The full lifting procedure, including the goodness test and the explicit delay analysis after filtering, must be written out and verified; an informal assertion is insufficient for a generalization of the Bougeret et al. dichotomy.
minor comments (2)
- [Abstract] Abstract: the phrase 'promising at the intersection' is grammatically incomplete; it should read 'promising field at the intersection'.
- [§2 or §3] The manuscript should clarify the precise relationship between the new PD-kernel definition and the two prior models (Creignou et al. and Golovach et al.) with a short comparison table of the three delay and correctness conditions.
Simulated Author's Rebuttal
We thank the referee for the careful and constructive review. The suggested clarifications will improve the rigor of the presentation. We address each major comment below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: [§4] §4 (generic framework): The central claim that any decision kernel for a vertex-subset problem yields a PD kernel of the same size rests on a lifting procedure that, given a kernel solution, decides in polynomial time whether it is 'good' and produces the corresponding original solutions without the enumeration order being destroyed by bad solutions. The manuscript must explicitly prove that the goodness test and lifting map run in time independent of the number of bad solutions; otherwise the polynomial-delay guarantee does not follow from the decision-kernel delay bound.
Authors: We agree that an explicit proof is required to establish the polynomial-delay guarantee. In the generic framework the decision kernel enumerates all (good and bad) solutions with polynomial delay. For each kernel solution the goodness test checks validity against the original instance using the reduction rules; this check runs in time polynomial in the kernel size and is therefore independent of the number of bad solutions. The lifting map then produces the corresponding original solutions in polynomial time per good solution. We will add a dedicated lemma in Section 4 that formally states and proves these time bounds, confirming that filtering bad solutions does not affect the delay between consecutive good solutions. revision: yes
-
Referee: [§5] §5 (Enum Vertex Cover, feedback-vertex-number case): The claim that the lifting algorithm 'requires only a few lines' is load-bearing for the asserted simplicity advantage over prior kernels. The full lifting procedure, including the goodness test and the explicit delay analysis after filtering, must be written out and verified; an informal assertion is insufficient for a generalization of the Bougeret et al. dichotomy.
Authors: We acknowledge that the informal description, while highlighting brevity, is insufficient for a rigorous generalization. The lifting procedure for the feedback-vertex-number parameterization consists of recovering the feedback vertex set from the kernel, verifying coverage on the resulting forest, and mapping back the cover. We will expand Section 5 with complete pseudocode for the algorithm, an explicit goodness test that discards invalid covers, and a detailed delay analysis showing that the per-solution filtering time remains polynomial in the input size. This will substantiate both the correctness of the polynomial-delay claim and the claimed simplicity relative to earlier kernels. revision: yes
Circularity Check
New PD-kernel model and generic lifting framework are defined independently without reduction to inputs or self-citations
full rationale
The paper defines the PD-kernel model explicitly as a relaxation of Golovach et al.'s polynomial-delay enumeration kernels, allowing bad solutions to be ignored while requiring polynomial-delay lifting of good ones. It then presents a generic framework (Section 4) that converts any decision kernel for vertex-subset problems into a PD kernel of the same size via a polynomial-time goodness test and lifting map. For Enum Vertex Cover, this is instantiated on existing kernels (e.g., for feedback vertex number parameterization, described as 'requiring only a few lines'). No equation or central claim reduces by construction to a fitted parameter, prior self-result, or ansatz smuggled via citation; the lifting delay bound is re-proven after filtering rather than assumed from the decision kernel alone. The generalized dichotomy follows directly from applying the framework to known decision kernels. The derivation chain is self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Polynomial-delay enumeration is well-defined and the lifting procedure can ignore bad solutions without violating the delay guarantee for good solutions.
Reference graph
Works this paper leans on
-
[1]
URL: https://www.sciencedirect.com/science/article/pii/S0022000016300812, doi:10.1016/j.jcss.2016.09.002. 31 Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van B. Le. Refined notions of parameterized enumeration kernels with applications to matching cut enumeration.Journal of Computer and System Sciences, 123:76–102, 2022.doi:10.1016/j.jcss....
-
[2]
URL:http://www.theses.fr/2010PA077178. 44Yann Strozecki. Enumeration complexity.Bulletin of EATCS, 3(129), 2019
work page 2019
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.