A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
From MaRDI portal
Publication:1672007
DOI10.1016/J.JCSS.2018.05.005zbMATH Open1402.68199arXiv1604.06056OpenAlexW2963729476WikidataQ115571246 ScholiaQ115571246MaRDI QIDQ1672007FDOQ1672007
O-joung Kwon, Eduard Eiben, Robert Ganian
Publication date: 7 September 2018
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Abstract: Vertex deletion problems ask whether it is possible to delete at most vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter tractable algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis. As an application of our algorithm, we show that a vertex deletion set to distance-hereditary graphs can be used as a parameter which allows single-exponential fixed-parameter tractable algorithms for classical NP-hard problems.
Full work available at URL: https://arxiv.org/abs/1604.06056
Recommendations
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- A polynomial kernel for distance-hereditary vertex deletion
- A polynomial kernel for distance-hereditary vertex deletion
- Parameterized vertex deletion problems for hereditary graph classes with a block property
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Distance in graphs (05C12)
Cites Work
- Fundamentals of parameterized complexity
- Finding odd cycle transversals.
- Fixed-parameter algorithms for cluster vertex deletion
- Which problems have strongly exponential complexity?
- Linear time solvable optimization problems on graphs of bounded clique-width
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- Approximating clique-width and branch-width
- Parameterized Algorithms
- Graph minors. V. Excluding a planar graph
- Distance-hereditary graphs
- Rank-width and vertex-minors
- A Combinatorial Decomposition Theory
- On the existence of subexponential parameterized algorithms
- Kernelization Using Structural Parameters on Sparse Graph Classes
- Decomposition of Directed Graphs
- Graph Layout Problems Parameterized by Vertex Cover
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- The Hamiltonian problem on distance-hereditary graphs
- Computing maximum stable sets for distance-hereditary graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Recognizing circle graphs in polynomial time
- Parameterized complexity of vertex deletion into perfect graph classes
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
- Transforming trees by successive local complementations
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
- On the extension of bipartite to parity graphs
- The behavior of clique-width under graph operations and graph transformations
- Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Solving Problems on Graphs of High Rank-Width
- Meta-kernelization using Well-structured Modulators
- A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- A polynomial kernel for block graph deletion
- A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
- A polynomial kernel for distance-hereditary vertex deletion
Cited In (10)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
- A polynomial kernel for 3-leaf power deletion
- A polynomial kernel for distance-hereditary vertex deletion
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Distance from triviality 2.0: hybrid parameterizations
- A polynomial kernel for distance-hereditary vertex deletion
- Graph reconstruction in the congested clique
This page was built for publication: A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1672007)
