A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
From MaRDI portal
(Redirected from Publication:1672007)
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.
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
Cites work
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- A Combinatorial Decomposition Theory
- A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
- A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
- A polynomial kernel for block graph deletion
- A polynomial kernel for distance-hereditary vertex deletion
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
- Approximating clique-width and branch-width
- Computing maximum stable sets for distance-hereditary graphs
- Decomposition of Directed Graphs
- Distance-hereditary graphs
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- Finding odd cycle transversals.
- Fixed-parameter algorithms for cluster vertex deletion
- Fundamentals of parameterized complexity
- Graph Layout Problems Parameterized by Vertex Cover
- Graph minors. V. Excluding a planar graph
- Kernelization using structural parameters on sparse graph classes
- Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
- Linear time solvable optimization problems on graphs of bounded clique-width
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Meta-kernelization using Well-structured Modulators
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- On the existence of subexponential parameterized algorithms
- On the extension of bipartite to parity graphs
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- Parameterized algorithms
- Parameterized complexity of vertex deletion into perfect graph classes
- Rank-width and vertex-minors
- Recognizing circle graphs in polynomial time
- Solving problems on graphs of high rank-width
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- The Hamiltonian problem on distance-hereditary graphs
- The behavior of clique-width under graph operations and graph transformations
- Transforming trees by successive local complementations
- Which problems have strongly exponential complexity?
Cited in
(11)- scientific article; zbMATH DE number 7765420 (Why is no real title available?)
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- A polynomial kernel for 3-leaf power deletion
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- A polynomial kernel for distance-hereditary vertex deletion
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Distance from triviality 2.0: hybrid parameterizations
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- 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)
