Bidimensionality and kernels
From MaRDI portal
Publication:5417643
zbMATH Open1288.68116arXiv1107.2221MaRDI QIDQ5417643FDOQ5417643
Authors: Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos 
Publication date: 22 May 2014
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.
Full work available at URL: https://arxiv.org/abs/1107.2221
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph minors (05C83)
Cited In (88)
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Packing cycles faster than Erdős-Pósa
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- First-Order Model-Checking in Random Graphs and Complex Networks
- Finite integer index of pathwidth and treewidth
- On the Parameterized Complexity of the Expected Coverage Problem
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Hitting weighted even cycles in planar graphs
- Domination above \(r\)-independence: does sparseness help?
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- Explicit linear kernels via dynamic programming
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- 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
- 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
- Compactors for parameterized counting problems
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- A linear kernel for a planar connected dominating set
- Kernelization: new upper and lower bound techniques
- A Retrospective on (Meta) Kernelization
- Contraction bidimensionality of geometric intersection graphs
- Lossy kernels for connected dominating set on sparse graphs
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- On the hardness of losing width
- On polynomial kernels for sparse integer linear programs
- Smaller kernels for several FPT problems based on simple observations
- Spanners in sparse graphs
- Title not available (Why is that?)
- On the parameterized complexity of the expected coverage problem
- Explicit linear kernels via dynamic programming
- Characterising bounded expansion by neighbourhood complexity
- Graph minors and parameterized algorithm design
- Bidimensionality and parameterized algorithms (invited talk)
- Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Data-compression for parametrized counting problems on sparse graphs
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- On the hardness of losing width
- Lossy kernels for connected dominating set on sparse graphs
- Contraction-bidimensionality of geometric intersection 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
- Implicit branching and parameterized partial cover problems
- A \(13k\)-kernel for planar feedback vertex set via region decomposition
- FPT algorithms for connected feedback vertex set
- Planar graph vertex partition for linear problem kernels
- Kernelization -- preprocessing with a guarantee
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Title not available (Why is that?)
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Contraction obstructions for treewidth
- A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Algorithmic properties of sparse digraphs
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
- Confronting intractability via parameters
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Meta-kernelization using well-structured modulators
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Algorithmic Learning Theory
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- Kernelization of packing problems
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- Towards optimal kernel for connected vertex cover in planar graphs
- Explicit linear kernels for packing problems
- On the parameterized complexity of finding separators with non-hereditary properties
- 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
- Title not available (Why is that?)
- A linear kernel for planar red-blue dominating set
- Hitting forbidden minors: approximation and kernelization
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Fixed-parameter tractability of treewidth and pathwidth
- Partial vertex cover on graphs of bounded degeneracy
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)
