Bidimensionality and kernels
From MaRDI portal
Publication:5417643
Abstract: In this paper we use several of the key ideas from Bidimensionality to give a new generic approach to design EPTASs and subexponential time parameterized algorithms for problems on classes of graphs which are not minor closed, but instead exhibit a geometric structure. In particular we present EPTASs and subexponential time parameterized algorithms for Feedback Vertex Set, Vertex Cover, Connected Vertex Cover, Diamond Hitting Set, on map graphs and unit disk graphs, and for Cycle Packing and Minimum-Vertex Feedback Edge Set on unit disk graphs. Our results are based on the recent decomposition theorems proved by Fomin et al [SODA 2011], and our algorithms work directly on the input graph. Thus it is not necessary to compute the geometric representations of the input graph. To the best of our knowledge, these results are previously unknown, with the exception of the EPTAS and a subexponential time parameterized algorithm on unit disk graphs for Vertex Cover, which were obtained by Marx [ESA 2005] and Alber and Fiala [J. Algorithms 2004], respectively. We proceed to show that our approach can not be extended in its full generality to more general classes of geometric graphs, such as intersection graphs of unit balls in R^d, d >= 3. Specifically we prove that Feedback Vertex Set on unit-ball graphs in R^3 neither admits PTASs unless P=NP, nor subexponential time algorithms unless the Exponential Time Hypothesis fails. Additionally, we show that the decomposition theorems which our approach is based on fail for disk graphs and that therefore any extension of our results to disk graphs would require new algorithmic ideas. On the other hand, we prove that our EPTASs and subexponential time algorithms for Vertex Cover and Connected Vertex Cover carry over both to disk graphs and to unit-ball graphs in R^d for every fixed d.
Recommendations
Cited in
(88)- Compactors for parameterized counting problems
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- A linear kernel for a planar connected dominating set
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- Kernelization: new upper and lower bound techniques
- Contraction bidimensionality of geometric intersection graphs
- A Retrospective on (Meta) Kernelization
- Packing cycles faster than Erdős-Pósa
- On polynomial kernels for sparse integer linear programs
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- On the hardness of losing width
- Lossy kernels for connected dominating set on sparse graphs
- Finite integer index of pathwidth and treewidth
- First-Order Model-Checking in Random Graphs and Complex Networks
- On the Parameterized Complexity of the Expected Coverage Problem
- Spanners in sparse graphs
- Smaller kernels for several FPT problems based on simple observations
- On the parameterized complexity of the expected coverage problem
- scientific article; zbMATH DE number 7764102 (Why is no real title available?)
- Characterising bounded expansion by neighbourhood complexity
- Explicit linear kernels via dynamic programming
- Graph minors and parameterized algorithm design
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Bidimensionality and parameterized algorithms (invited talk)
- Hitting weighted even cycles in planar graphs
- Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
- Data-compression for parametrized counting problems on sparse graphs
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- On the hardness of losing width
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Lossy kernels for connected dominating set on sparse graphs
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Kernelization using structural parameters on sparse graph classes
- Contraction-bidimensionality of geometric intersection graphs
- Implicit branching and parameterized partial cover problems
- A 13k-kernel for planar feedback vertex set via region decomposition
- Planar graph vertex partition for linear problem kernels
- FPT algorithms for connected feedback vertex set
- Kernelization -- preprocessing with a guarantee
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Contraction obstructions for treewidth
- scientific article; zbMATH DE number 6783430 (Why is no real title available?)
- Domination above \(r\)-independence: does sparseness help?
- A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Algorithmic properties of sparse digraphs
- Confronting intractability via parameters
- Explicit linear kernels via dynamic programming
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Meta-kernelization using well-structured modulators
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
- Planar \(k\)-path in subexponential time and polynomial space
- Sparse obstructions for minor-covering parameters
- Algorithmic Learning Theory
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- Towards optimal kernel for connected vertex cover in planar graphs
- On the parameterized complexity of finding separators with non-hereditary properties
- Explicit linear kernels for packing problems
- Kernelization of packing problems
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
- Edge-disjoint packing of stars and cycles
- Linear kernels for outbranching problems in sparse digraphs
- On kernelization and approximation for the vector connectivity problem
- Large Induced Subgraphs via Triangulations and CMSO
- Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
- Improved kernel results for some FPT problems based on simple observations
- Kernels for packing and covering problems
- Bidimensionality and kernels
- A linear kernel for planar red-blue dominating set
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Hitting forbidden minors: approximation and kernelization
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- Fixed-parameter tractability of treewidth and pathwidth
- Partial vertex cover on graphs of bounded degeneracy
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
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 Q5417643)
