Bidimensionality and kernels
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- (Meta) kernelization
- A 4k^2 kernel for feedback vertex set
- A Linear Kernel for Planar Feedback Vertex Set
- A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
- A partial k-arboretum of graphs with bounded treewidth
- A Separator Theorem for Nonplanar Graphs
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Bidimensional Parameters and Local Treewidth
- Bidimensionality and kernels
- Bidimensionality and parameterized algorithms (invited talk)
- Bidimensionality of geometric intersection graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Contraction obstructions for treewidth
- Contraction-bidimensionality of geometric intersection graphs
- Data-compression for parametrized counting problems on sparse graphs
- Easy problems for tree-decomposable graphs
- Excluded grid minors and efficient polynomial-time approximation schemes
- Excluded grid theorem: improved and simplified
- Explicit linear kernels for packing problems
- Explicit linear kernels via dynamic programming
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
- Fundamentals of parameterized complexity
- Graph minors and parameterized algorithm design
- Graph minors. III. Planar tree-width
- Graph minors. V. Excluding a planar graph
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Handbook of Graph Grammars and Computing by Graph Transformation
- scientific article; zbMATH DE number 1323192 (Why is no real title available?)
- scientific article; zbMATH DE number 475614 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 6783430 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Kernelization and Sparseness: the case of Dominating Set
- Kernelization. Theory of parameterized preprocessing
- Kernels for (connected) dominating set on graphs with excluded topological minors
- Linear Kernel for Planar Connected Dominating Set
- Linear kernels for edge deletion problems to immersion-closed graph classes
- Linearity of grid minors in treewidth with applications through bidimensionality
- Lower bounds on kernelization
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
- Nonserial dynamic programming
- On the Induced Matching Problem
- Parameterized algorithms
- Parameterized complexity: exponential speed-up for planar graph problems
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Parametrized complexity theory.
- Planar Separators
- Polynomial bounds for the grid-minor theorem
- Polynomial bounds for the grid-minor theorem
- Polynomial-time data reduction for dominating set
- Recent developments in kernelization: a survey
- Reduction algorithms for graphs of small treewidth
- S-functions for graphs
- Solving d-SAT via Backdoors to Small Treewidth
- Subexponential parameterized algorithms
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
- Vertex cover: Further observations and further improvements
Cited in
(16)- Twin-width and polynomial kernels
- Contraction Bidimensionality: The Accurate Picture
- Bidimensionality and parameterized algorithms (invited talk)
- scientific article; zbMATH DE number 6783430 (Why is no real title available?)
- Bidimensionality and kernels
- Algorithmic Learning Theory
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
- Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
- Kernelization for counting problems on graphs: preserving the number of minimum solutions
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Kernelization for counting problems on graphs: preserving the number of minimum solutions
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Boundaried kernelization
- Enumeration kernels for vertex cover and feedback vertex set
- Dominating set with quotas: balancing coverage and constraints
This page was built for publication: Bidimensionality and kernels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387764)
