Source-linked AI summary
(Meta) Kernelization
Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos
TL;DR
The paper asks how broad classes of hard parameterized graph problems can receive compact equivalent instances on bounded-genus graphs. It develops meta-theorems based on CMSO expressibility, coverability, finite integer index, and protrusion reductions, obtaining polynomial kernels and, under stronger structural conditions, linear kernels. These results provide a uniform explanation for many known planar-graph kernelization results while identifying coverability as a necessary scope condition.
Problem
The paper addresses the need for general kernelization results that explain and extend polynomial and linear kernels for parameterized problems on bounded-genus graphs.
Method
The paper combines CMSO-based reduction rules, graph decompositions, algebraic reductions, and protrusion replacement, with finite integer index used for linear kernels.
Results
The theorems give polynomial kernels for suitable r-coverable CMSO problems and linear kernels for r-quasi-coverable problems with finite integer index.
Takeaways & Limitations
The meta-theorems uniformly explain and generalize many known linear kernelization results for parameterized graph problems on surfaces.
Takeaways & Limitations
Coverability or quasi-coverability cannot be omitted: some first-order definable planar problems lack polynomial kernels unless coNP ⊆ NP/poly.
Abstract
from arXiv · showhide
In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this work we give two meta-theorems on kernelzation. The first theorem says that all problems expressible in Counting Monadic Second Order Logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.
1 Introduction
The introduction frames kernelization as polynomial-time size reduction and develops meta-theorems for bounded-genus graph problems. The results obtain polynomial kernels from CMSO expressibility and coverability, and linear kernels from finite integer index with quasi-coverability.
- Kernelization reduces a parameterized instance in polynomial time to an equivalent instance of size polynomial in k; O(k) size gives a linear kernel.
- The paper studies meta-theorems connecting logical definability, graph structure, and kernelization on graphs embedded in surfaces of bounded genus.
- Annotated r-coverable p-min/max-CMSO[ψ] problems admit quadratic kernels, while annotated p-eq-CMSO[ψ] problems admit cubic kernels.
- NP-hard r-coverable p-min/eq/max-CMSO[ψ] problems whose annotated versions are in NP admit polynomial kernels.
- Problems with finite integer index and r-quasi-coverability admit linear kernels, unifying and generalizing known linear surface-graph kernels.
- The proofs combine graph decomposition with algebraic reductions, using protrusions of constant treewidth separated by a constant-size boundary.For coverable problems, bounded-genus graphs covered by k constant-radius balls admit protrusion decompositions with O(k) parts.
2 Definitions and Notations
This section defines parameterized graph problems, kernelization, graph-structural notions, and finite-index equivalence used throughout the paper.
- Parameterized problems: A parameterized instance consists of an encoded graph and parameter k, with negative-parameter instances required to share a uniform membership status.The paper also permits annotated graph instances, where solutions are restricted to a specified vertex set.
- Kernelization: A kernelization algorithm maps an instance to an equivalent instance in polynomial time whose encoding and parameter are bounded by g(k).Polynomial and linear kernels correspond respectively to g(k)=k^O(1) and g(k)=O(k).
- Graph structure: Tree decompositions represent graphs by tree-indexed vertex bags, and treewidth is the minimum possible maximum bag size minus one.Any tree decomposition can be transformed into a nice tree decomposition in linear time.
- Boundaried graphs: Boundaried graphs carry labelled terminal vertices and can be glued by identifying terminals with equal labels.These operations support equivalence relations that compare graph pieces under arbitrary compatible gluings.
- Finite-index equivalence: The canonical equivalence relation for a parameterized graph problem preserves membership under all gluings after an additive parameter shift.Each equivalence class has a progressive representative whose shift is non-positive.
3 A variant of Courcelle’s Theorem
The section establishes a finite-state characterization for CMSO-definable properties on boundaried structures, enabling compatibility decisions from finite signatures.
- Equivalence framework: Compatibility equivalence groups boundaried structures that behave identically when combined with every compatible structure.The canonical equivalence for a CMSO sentence is defined through compatibility and the sentence’s truth on glued structures.
- Finite-state property: Every CMSO-definable property on structures has finitely many equivalence classes for each fixed arity and finite index set.This is the section’s central finite-state lemma.
- Signatures: A signature function sgnψ encodes bounded information about a boundaried structure, including compatibility data and selected variable assignments.For fixed atomic formula, arity, and index set, the signature length depends only on those fixed quantities.
- Decoding: A decoder decψ uses the signature and the compatible structure to determine whether the CMSO property holds after gluing.The decoder is defined to reject null signatures or incompatible types and to evaluate compatible cases compositionally.
- Correctness: For vertex-set membership, the procedure returns true exactly when the glued assignment satisfies the formula, without accessing the original structure directly.The same signature-based approach handles edge variables, set variables, and other atomic cases.
4 Derivation of our results
The section derives kernelization from protrusion replacement and decomposition properties, yielding polynomial kernels generally and linear kernels under finite integer index.
- Protrusions: A t-protrusion has boundary size and treewidth at most t; protrusion replacement algorithms shrink sufficiently large protrusions while preserving equivalence.The replacement family may also ensure that the parameter does not increase.
- Structural properties: Property A supplies protrusion replacement, while properties B and B* supply full and weak protrusion decompositions for YES-instances.The weak property applies when all sufficiently small-boundary protrusions are already bounded in size.
- Meta-algorithm: The meta-kernelization procedure repeatedly replaces large low-treewidth regions and outputs an equivalent graph in which every i-protrusion has size at most f(2i)·k^a.Its running time is |I|^O(t).
- Master theorems: If properties A and B hold with replacement exponent a, the master theorem gives a kernel of size O(k^a+1).The construction uses Meta-kernelization(c) and runs in polynomial time for fixed decomposition constant c.
- Applications: When a=0, the weaker property B* suffices, yielding a linear kernel.Finite integer index gives a=0 replacement, while CMSO optimization variants give a=1 or a=2.
- Applications: Coverable problems satisfy B and quasi-coverable problems satisfy B*, connecting these structural conditions to the paper’s kernelization results.The resulting framework applies to the corresponding CMSO and finite-integer-index problem classes.
5 Reduction Rules
The section develops protrusion-based reduction rules for annotated CMSO problems and problems with finite integer index, yielding smaller equivalent instances under explicit size and runtime conditions.
- Model checking on structures: Proposition 5.1 solves Min/Max/Eq-CMSO on structures in f(tw(Gα), |ψ|) · |V (Gα)| steps.The bound depends on the structure's treewidth and the CMSO sentence length.
- Protrusion replacement families: Annotated CMSO reduction rules first reduce annotated vertices, then partition protrusions, and finally replace a largest protrusion with an equivalent smaller boundaried graph.For annotated p-min-CMSO[ψ], these steps correspond to Lemmata 5.3, 5.4, and 5.6.
- Protrusion replacement families: O(k) annotated vertices remain inside a t-protrusion for p-min-CMSO[ψ], after an O(|X|)-step equivalent reduction.The constants hidden in the O-notation depend only on |ψ| and t.
- Protrusion replacement families: A t-protrusion with more than c2k vertices admits an O(|X|)-step equivalent reduction for annotated p-min-CMSO[ψ].The reduced instance has fewer vertices, and c2 depends only on |ψ| and t.
- Annotated p-eq-CMSO[ψ]: For annotated p-eq-CMSO[ψ], the corresponding bounds are O(k2) annotated vertices, a threshold c2k2, and O(k · |X|) reduction time.The problem has protrusion replacement property A for a = 2.
- Annotated p-max-CMSO[ψ] and FII: For annotated p-max-CMSO[ψ], the rules retain O(k) annotated vertices and reduce sufficiently large protrusions in O(|X|) steps; FII rules also reduce protrusions in O(|X|) steps.The p-max and FII replacement properties have a = 1 and a = 0, respectively.
6 Combinatorial results
The section develops decomposition lemmas for coverable and quasi-coverable problems on bounded-genus graphs. Coverability yields protrusion decompositions directly, while quasi-coverability yields weak decompositions through treewidth and separation arguments.
- Coverable problems: Every r-coverable problem has the protrusion decomposition property B.This follows from a decomposition theorem for bounded-genus graphs whose vertices are covered by O(k) constant-radius balls.
- Coverable problems: If vertices are covered by at most k radius-r balls, the graph admits a protrusion decomposition with constants depending only on r and the genus.The construction contracts breadth-first trees rooted at covering vertices and simplifies the resulting embedded graph using Euler’s formula.
- Coverable problems: Each component outside the central region has bounded treewidth, and the resulting protrusions have O(k) total count and bounded boundary size.The component-treewidth bound is f1(4r + 2, g), while Euler’s formula gives q = O(k) protrusion pieces.
- Quasi-coverable problems: Every r-quasi-coverable problem has the weak protrusion decomposition property B∗.The proof uses a treewidth-obstruction lemma: distant regions that resist small separation force large treewidth.
- Quasi-coverable problems: A quasi-coverable graph either contains a sufficiently large protrusion suitable for reduction or admits a decomposition with O(k)-scale control.The argument derives a bounded-radius dominating set of size O(k) for YES-instances without large protrusions, converting them into coverable instances.
7 Criteria for proving FII
This section provides criteria for proving finite integer index. Strong monotonicity supplies finite signatures for CMSO optimization problems, which establish FII and remain compatible with CMSO-definable graph restrictions.
- Strong monotonicity: Strong monotonicity requires one set W whose feasibility and objective value approximate every feasible boundaried completion within f(|I|).For minimization, |W| ≤ ζG(G′, S′) + f(|I|); for maximization, |W| ≥ ζG(G′, S′) − f(|I|).
- Strong monotonicity: Strongly monotone p-min-CMSO[ψ] and p-max-CMSO[ψ] problems have finite integer index.The proof represents boundaried graphs by signatures with finitely many equivalence classes and transfers solutions across equivalent boundaried graphs with a constant parameter shift.
- Signature argument: Finite signatures encode normalized completion costs, and equivalent signatures imply equivalent boundaried graphs up to an additive parameter constant.The construction uses finitely many representative structures and establishes the equivalence in both directions.
- Scope of the criterion: The strong-monotonicity criterion is sufficient rather than necessary, since some minimization problems can have FII without being strongly monotone.The section notes that such examples require criteria beyond Lemma 7.3.
- Graph-class restrictions: FII is preserved when restricting a parameterized problem to any CMSO-definable graph class.The bounded-genus restriction is an application because excluding each fixed-genus obstruction can be expressed in CMSO.
8 Implications of our results
The paper applies its meta-theorems to broad families of bounded-genus graph problems. It establishes coverability, quasi-coverability, and FII for deletion, packing, domination, and related problems, yielding the corresponding kernelization framework.
- Deletion problems: For every fixed genus, p-H-Deletion is quasi-coverable and has FII when H is finite, connected, and contains a planar graph.Planarity of one excluded minor bounds the treewidth of the graph after deleting a solution, while CMSO definability and strong monotonicity provide FII.
- Deletion problems: The p-H-Deletion framework includes Vertex Cover, Feedback Vertex Set, Diamond Hitting Set, Almost Outerplanar, and almost bounded-treewidth or pathwidth problems.Each is obtained by choosing an appropriate finite excluded-minor set H.
- Packing problems: For every fixed genus, p-H-Packing is quasi-coverable, and p-Cycle Packing has FII.The packing analysis relates packing to deletion through the minimum set hitting all minor models.
- Domination problems: Several domination problems are coverable and have FII, including r-Dominating Set, q-Threshold Dominating Set, Efficient Dominating Set, and Connected Dominating Set.These results instantiate both structural properties required by the meta-theorems.
8.6 Scattered sets
The scattered-set applications define r-independent sets and use boundary characteristics to prove FII. They also establish coverability for bounded-genus scattered-set instances and extend the framework to directed domination problems.
- Scattered-set framework: An r-independent set contains vertices whose pairwise distances exceed r; p-r-Scattered Set asks whether at least k such vertices exist.The problem is parameterized by the requested set size k.
- Scattered-set framework: For every fixed r and genus, bounded-genus r-Scattered Set has the r-coverability property and FII.The coverability proof uses an r-dominating set of size O(k), while FII follows from a three-stage boundary-signature argument.
- FII proof: Boundary signatures record labels, truncated inter-boundary distances, and normalized maximum sizes of feasible r-independent sets.Equivalent signatures yield equivalent boundaried graphs up to an additive constant in the parameter.
- FII proof: The refinement argument transfers an r-independent set through a boundaried replacement while preserving feasibility and adjusting the threshold by a constant.The proof removes vertices close to the boundary, then combines the remaining set with the completion outside the replaced piece.
- Directed extensions: The directed extensions cover independent directed domination and maximum internal out-branching, while directed domination additionally has FII.Coverability is defined through the underlying undirected graph.
8.9 Summary of consequences of our results
The section applies the meta-theorems to many parameterized graph problems on bounded-genus graphs, yielding linear or polynomial kernels according to their structural properties.
- Minimization problems with FII and quasi-coverability: A broad family of minimization problems with FII and quasi-coverability admits linear kernels on graphs of bounded genus.The family includes Vertex Cover, Feedback Vertex Set, Dominating Set variants, H-Deletion, and related problems.
- Minimization problems with FII and quasi-coverability: The p-S-Covering, p-Minimum Partition Into Cliques, p-Edge Clique Cover, and p-s-Cycle Transversal problems also obtain linear kernels through coverability, FII, and problem-specific preprocessing arguments.The p-Edge Clique Cover case uses quasi-coverability, while p-s-Cycle Transversal requires removing vertices absent from all cycles of length at most s.
- Maximization problems with FII: A listed family of maximization problems with FII, including p-Independent Set, p-Cycle Packing, and p-Triangle Vertex Packing, admits linear kernels.Some examples are quasi-coverable rather than coverable, and several are not strongly monotone.
- Problems without FII: Problems lacking FII can still admit polynomial kernels when they satisfy the CMSO and coverability conditions of Theorem 1.1.The listed examples include p-Independent Dominating Set, p-Acyclic Dominating Set, p-Independent Directed Domination, p-Maximum Internal Out-branching, p-Odd Set, and p-Edge-S-Covering.
- Limitations and non-applicable problems: The framework has explicit boundaries: p-Longest Path and p-Longest Cycle lack polynomial kernels unless coNP ⊆ NP/poly, while p-Hamiltonian Path Completion is not quasi-coverable and cannot have a kernel unless P=NP.p-Maximum Cut is quasi-coverable and has a trivial 2k kernel on general graphs, but it does not have FII.
9 Open Problems and Further Directions
The paper identifies extensions of its logical and combinatorial framework, broader graph classes, practical kernel engineering, and concrete problems that remain unresolved.
- Further extensions: Coverability or quasi-coverability is necessary for the stated framework: even first-order definable k-Path lacks a polynomial kernel on planar graphs unless coNP ⊆ NP/poly.The paper asks whether its properties can extend to larger problem classes.
- Further extensions: Whether all quasi-coverable CMSO problems admit linear kernels on bounded-genus graphs remains an open question, including for planar graphs.This is posed explicitly as a future research problem.
- Further extensions: Natural graph-class extensions include graphs of bounded local treewidth and bounded expansion, with an initial step already identified.
- Practical considerations: Direct meta-theorem applications may have larger constants than tailor-made kernels, although protrusion replacement could support computer-aided reduction-rule design.Obtaining linear kernels with reasonably small constants remains a research goal.
- Concrete open problems: p-Directed Feedback Vertex Set and p-Odd Cycle Transversal remain unresolved because they are CMSO-expressible but not known to be quasi-coverable.No polynomial kernel is known for the former on planar graphs, and a deterministic planar kernel remains open for the latter.
- Impact: Protrusion replacement has since been used for kernels on H-minor-free, unit disc, and topological-minor-free graph classes.
A Problem Compendium
The compendium records the kernelization status of the problems discussed in the paper.
- A Problem Compendium: The compendium presents the kernelization status of all problems mentioned in the paper.
A.1 Minimization problems that have FII and are quasi-coverable – linear kernels for graphs of bounded genus.
The compendium section lists problems receiving linear kernels through the paper’s bounded-genus meta-theorem consequences.
- A.1 Minimization problems that have FII and are quasi-coverable – linear kernels for graphs of bounded genus.: The listed problems include Vertex Cover, Feedback Vertex Set, several domination variants, H-Deletion, Connected Vertex Cover, p-S-Covering, and p-s-Cycle Transversal.
A.2 Maximization problems that have FII and are quasi-coverable – linear kernels for graphs of bounded genus.
This section lists problems with finite integer index (FII) and distinguishes how that property is established and when preprocessing is assumed.
- The listed problems include Scattered Set, Independent Set, Induced Matching, Triangle Edge Packing, and several packing and spanning-tree problems.The list also includes Maximum Internal Spanning Tree, Maximum Full-Degree Spanning Tree, Cycle Packing, H-Packing, Triangle Vertex Packing, S-Packing, and Edge Cycle Packing.
- For problems marked with an asterisk, the FII property requires a direct proof.
- For the remaining problems, FII follows by expressing them as p-min/max-CMSO problems and proving strong monotonicity.
- For problems marked with a cross, the linear-kernel result assumes application of a preprocessing routine.
A.3 Problems that do not have FII and are coverable p-min/max-CMSO – polynomial kernels for graphs of bounded genus.
This section lists problems that lack finite integer index but are coverable p-min/max-CMSO problems.
- The listed problems are p-Independent Dominating Set, p-Acyclic Dominating Set, and p-Independent Directed Domination.
- The list also includes p-Maximum Internal Out-branching, p-Odd Set, and p-Edge-S-Covering.
A.4 A problem that has FII but is not quasi-coverable.
This section identifies p-Hamiltonian Path Completion as a problem that has finite integer index but is not quasi-coverable.
- The problem considered in this section is p-Hamiltonian Path Completion.
A.6 Problems that do not have FII and they are not quasi-coverable.
This section identifies p-Longest Path and p-Longest Cycle as problems that lack finite integer index and are not quasi-coverable.
- The problems listed are p-Longest Path and p-Longest Cycle.