Source-linked AI summary
Bidimensionality and Kernels
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos
TL;DR
The paper addresses whether bidimensionality can yield linear kernels beyond the graph classes covered by earlier kernelization analyses. It combines bidimensionality, separability, CMSO expressibility, protrusion decompositions, and finite integer index to prove linear-kernel results. The main theorem covers minor-bidimensional problems on fixed-minor-free graphs and contraction-bidimensional problems on apex-minor-free graphs, with many applications.
Problem
Earlier bidimensionality applications established subexponential parameterized algorithms and PTASs, but the paper investigates its third direction: linear kernels for parameterized problems.
Method
The paper derives protrusion decompositions from bidimensionality and separability, then applies CMSO-based finite integer index reduction rules to shrink protrusions.
Results
Theorem 1.1 proves linear kernels for CMSO-definable linear-separable minor-bidimensional problems on fixed-minor-free graphs and contraction-bidimensional problems on fixed apex-minor-free graphs.
Takeaways & Limitations
The theorem yields linear kernels for many problems, including Treewidth-η-Modulator, domination, covering, packing, and Feedback Vertex Set variants on the stated graph classes.
Takeaways & Limitations
For separable contraction-bidimensional CMSO-definable problems, the technique guarantees linear kernels on H-minor-free graphs only when H is an apex graph.
Abstract
from arXiv · showhide
Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005), pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005, pp.590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems g graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.
1 Introduction
This section positions bidimensionality as a framework extended from subexponential algorithms and PTASs to kernelization, establishing linear-kernel meta-theorems under structural and logical conditions.
- Background: Bidimensionality was developed to unify subexponential fixed-parameter algorithms across planar, bounded-genus, and fixed-minor-free graph classes.A problem is roughly bidimensional when its solution value on a k × k grid is Ω(k^2).
- Background: Bidimensionality later yielded PTASs for problems satisfying separation properties on planar and other sparse graph classes.
- Contribution: This paper establishes kernelization as a third application of bidimensionality theory for parameterized problems.Kernelization studies polynomial-time reductions preserving the answer while bounding instance size by a function of the parameter.
- Main result: Every CMSO-definable, linear-separable minor-bidimensional problem has a linear kernel on graphs excluding a fixed graph as a minor.
- Main result: Every CMSO-definable, linear-separable contraction-bidimensional problem has a linear kernel on graphs excluding a fixed apex graph as a minor.
- Proof approach: The proof derives protrusion decompositions from bidimensionality, separability, and excluded-grid variants, avoiding embedding-dependent topological decompositions.The kernelization then replaces constant-treewidth protrusions using a finite-integer-index reduction rule.
2 Preliminaries
The preliminaries define graph-theoretic foundations, parameterized problems, kernelization, bidimensionality, and separation properties used later for linear-kernel results.
- Treewidth: A tree decomposition uses bags covering vertices and edges while the bags containing each vertex induce a subtree; treewidth is the minimum maximum bag size minus one.
- Separators and separations: A separation partitions a graph into two overlapping parts with no edges between their exclusive vertices; it is 2/3-balanced for Q when each exclusive part contains at most 2/3|Q| vertices.
- Separators and separations: Every graph has a 2/3-balanced separation of (G,S) whose order is at most tw(G) + 1.
- Minors and contractions: A contraction repeatedly contracts edges, whereas a minor is obtained by contracting a subgraph; graph classes may be closed under subgraphs, minors, or contractions.
- Parameterized graph problems and kernelization: Kernelization polynomially reduces an instance to an equivalent one whose output size plus parameter is bounded by a computable function of the original parameter.
- Parameterized graph problems: Cycle Packing can be represented as a vertex subset problem by requiring each component of an induced subgraph to be a cycle containing exactly one selected vertex, despite feasibility checking being NP-complete.
3 Decomposing into protrusions
The section derives protrusion decompositions for linearly separable bidimensional problems by first obtaining linear-size treewidth modulators and then decomposing the remaining graph into bounded-treewidth protrusions.
- Decomposition strategy: The technical strategy first proves linear-size treewidth modulators and then converts them into protrusion decompositions.The decomposition theorem is established in two stages: modulator construction followed by protrusion decomposition.
- Parameter-treewidth bounds: For minor-bidimensional problems, treewidth is bounded by α · (OPTΠ(G))^µ for constants α > 0 and 1/2 ≤ µ < 1.This follows from the SQGM property and minor-bidimensionality.
- Parameter-treewidth bounds: For contraction-bidimensional problems, the analogous treewidth bound holds on connected graphs under the SQGC property, with the connectivity condition needed in the general lemma.Separability later removes the connectivity requirement for the relevant extension.
- Applications: The framework covers many problems, including r-Dominating Set, Connected Dominating Set, Vertex Cover, Independent Set, Feedback Vertex Set, Cycle Packing, and Treewidth-η-Modulator.These problems are identified as contraction- or minor-bidimensional and linearly separable.
- Treewidth modulators: Linearly separable problems admit treewidth-η modulators whose size is at most ε · OPTΠ(G), for a suitable constant η and every ε > 0.This is shown for both minor-bidimensional and contraction-bidimensional problems under their respective SQG properties.
- Protrusion decomposition: A treewidth-η modulator can be extended to a protrusion decomposition with bounded protrusion width and the modulator contained in the core.For any ε > 0, the resulting decomposition has core size at most (1 + ε)|S| and some constant protrusion width r.
- Protrusion decomposition: The main theorem yields a (c·k, c)-protrusion decomposition for every graph in the class, where k = OPTΠ(G).The result applies to minor-bidimensional problems on SQGM classes and contraction-bidimensional problems on SQGC classes.
4 Finite index and finite integer index
This section develops finite-state and finite-integer-index machinery for CMSO problems on boundaried graphs. It proves that separable CMSO optimization problems have finite integer index.
- Definitions: The paper defines boundaried graphs, their labeled boundaries, annotated variants, and gluing by identifying equally labeled boundary vertices.These constructions provide the compositional setting for comparing graph pieces.
- Finite index: CMSO-definable predicates induce a finite-state equivalence relation on annotated boundaried graphs with any fixed finite label set.Finite state means that the relation has finitely many equivalence classes for each finite label set.
- Finite integer index: Finite integer index extends this comparison to parameterized problems by allowing a constant shift in the parameter after gluing equivalent boundaried graphs.The equivalence also requires equal label sets and preserves membership under every compatible boundaried context.
- Finite integer index: For separable CMSO minimization or maximization problems, the paper proves finite integer index by encoding each boundaried graph through finitely many representative-based values.The auxiliary functions are bounded by the separability function, yielding finitely many possible signatures.
- Finite integer index: The proof shows that the auxiliary equivalence relation refines the problem equivalence, so its finite number of classes establishes finite integer index.The parameter transposition constant is the difference between the two boundaried graphs’ optimum values.
5 Proof of the main theorem: Putting things together
The main theorem combines protrusion decomposition with finite integer index. FII supplies constant-size replacements, while bidimensionality supplies the decomposition needed for a linear kernel.
- Framework: The kernelization framework uses protrusion replacement and protrusion decomposition as its two required structural properties.The replacement property shrinks sufficiently large protrusions, while decomposition partitions yes-instances into controlled protrusions.
- Framework: A problem with properties A and B admits a kernel of size O(k^{a+1}).Property A is parameterized by a nonnegative constant a; property B uses a constant c.
- Protrusion replacement: Finite integer index gives protrusion replacement with a = 0, using a reduction rule that replaces a protrusion by one of constant size.This is the same general reduction-rule framework used in earlier bounded-genus kernelization work.
- Putting things together: For linear-separable minor-bidimensional problems on H-minor-free graphs, the proof obtains SQGM, FII, protrusion replacement, and protrusion decomposition.The master theorem then yields a linear kernel.
- Putting things together: The contraction-bidimensional case follows by an almost identical proof, with the theorem applying to classes excluding a fixed apex graph as a minor.The distinction between the two cases is part of the main theorem’s graph-class scope.
6 Conclusion
The conclusion relates the new results to earlier bounded-genus kernelization, notes linear-time implementation, and identifies limitations beyond apex-minor-free graphs. It also refines quasi-coverability results.
- Bidimensionality vs. quasi-coverability: Radial coverability implies radial quasi-coverability, but the converse need not hold.The distinction concerns whether a bounded-radius neighborhood around the covering set also controls the remaining treewidth.
- Bidimensionality vs. quasi-coverability: The paper’s techniques transform quasi-coverable problems into contraction-bidimensional separable problems whose optimum is O(k) on yes-instances.This provides a route from quasi-coverability to the bidimensionality framework.
- Bidimensionality vs. quasi-coverability: The refined framework subsumes earlier linear and polynomial kernel results for quasi-coverable problems on graphs of bounded genus.The argument transfers a protrusion decomposition from the constructed problem back to the original problem.
- Running time: The kernelization algorithms can run in time linear in the input size when using a fast protrusion replacer.The theorem statement itself leaves running time unspecified because replacement costs depend on the implementation.
- Open question: For contraction-bidimensional CMSO problems, the general technique currently guarantees linear kernels on H-minor-free graphs only when H is apex.Finding broader conditions for polynomial kernels beyond apex-minor-free graphs remains open.