Bidimensionality and kernels
From MaRDI portal
Publication:3387764
DOI10.1137/16M1080264zbMATH Open1475.05161arXiv1606.05689OpenAlexW3116379639MaRDI QIDQ3387764FDOQ3387764
Authors: Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos 
Publication date: 13 January 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1606.05689
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)
Cites Work
- Fundamentals of parameterized complexity
- Applications of a Planar Separator Theorem
- A partial k-arboretum of graphs with bounded treewidth
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Title not available (Why is that?)
- Easy problems for tree-decomposable graphs
- Recent developments in kernelization: a survey
- Parameterized algorithms
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- Nonserial dynamic programming
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- A Separator Theorem for Planar Graphs
- A Separator Theorem for Nonplanar Graphs
- Bidimensionality and kernels
- Handbook of Graph Grammars and Computing by Graph Transformation
- Polynomial bounds for the grid-minor theorem
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- S-functions for graphs
- Excluded grid theorem: improved and simplified
- A Linear Kernel for Planar Feedback Vertex Set
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- Title not available (Why is that?)
- Graph minors. III. Planar tree-width
- Explicit linear kernels for packing problems
- Bidimensionality: new connections between FPT algorithms and PTASs
- Title not available (Why is that?)
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Linear Kernel for Planar Connected Dominating Set
- Subexponential parameterized algorithms
- Vertex cover: Further observations and further improvements
- Title not available (Why is that?)
- Kernelization and Sparseness: the case of Dominating Set
- Planar Separators
- Contraction obstructions for treewidth
- Linearity of grid minors in treewidth with applications through bidimensionality
- Title not available (Why is that?)
- Bidimensional Parameters and Local Treewidth
- Parameterized complexity: exponential speed-up for planar graph problems
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
- Lower bounds on kernelization
- Reduction algorithms for graphs of small treewidth
- Explicit linear kernels via dynamic programming
- A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
- On the Induced Matching Problem
- (Meta) kernelization
- Solving d-SAT via Backdoors to Small Treewidth
- Graph minors and parameterized algorithm design
- Kernelization. Theory of parameterized preprocessing
- Data-compression for parametrized counting problems on sparse graphs
- Bidimensionality and parameterized algorithms (invited talk)
- Bidimensionality of geometric intersection graphs
- Excluded grid minors and efficient polynomial-time approximation schemes
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
- Contraction-bidimensionality of geometric intersection graphs
- Linear kernels for edge deletion problems to immersion-closed graph classes
- Polynomial bounds for the grid-minor theorem
- Kernels for (connected) dominating set on graphs with excluded topological minors
Cited In (8)
- Contraction Bidimensionality: The Accurate Picture
- Bidimensionality and parameterized algorithms (invited talk)
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- Title not available (Why is that?)
- Bidimensionality and kernels
- Algorithmic Learning Theory
- Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
- Twin-width and polynomial kernels
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)
