Vertex deletion problems on chordal graphs
From MaRDI portal
Publication:1786595
Abstract: Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.
Recommendations
Cites work
- scientific article; zbMATH DE number 3152801 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1496855 (Why is no real title available?)
- scientific article; zbMATH DE number 3322854 (Why is no real title available?)
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Approximation and kernelization for chordal vertex deletion
- Chordal editing is fixed-parameter tractable
- Chordal editing is fixed-parameter tractable
- Computing the Minimum Fill-In is NP-Complete
- Dominating sets for split and bipartite graphs
- Feedback vertex set inspired kernel for chordal vertex deletion
- Fixed-parameter tractability of graph modification problems for hereditary properties
- HAMILTONian circuits in chordal bipartite graphs
- Large Induced Subgraphs via Triangulations and CMSO
- Largest chordal and interval subgraphs faster than \(2^n\)
- Linear recognition of almost interval graphs
- Measuring indifference: unit interval vertex deletion
- Node-Deletion Problems on Bipartite Graphs
- On rigid circuit graphs
- On split-coloring problems
- On the hardness of approximating minimization problems
- On the pathwidth of chordal graphs
- Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
- Some simplified NP-complete graph problems
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The maximum k-colorable subgraph problem for chordal graphs
- The node-deletion problem for hereditary properties is NP-complete
- Trivially perfect graphs
- \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
Cited in
(21)- On the complexity of singly connected vertex deletion
- On the \(d\)-claw vertex deletion problem
- Vertex deletion on split graphs: beyond 4-hitting set
- Tight running time lower bounds for vertex deletion problems
- Algorithms and complexity of \(s\)-club cluster vertex deletion
- Vertex deletion problems on chordal graphs
- Node-and edge-deletion NP-complete problems
- Deletion graph problems based on deadlock resolution
- Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
- On some simplicial elimination schemes for chordal graphs
- Graph modification problem for some classes of graphs
- The vertex leafage of chordal graphs
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- Algorithms for deletion problems on split graphs
- Proper Interval Vertex Deletion
- A tight approximation algorithm for the cluster vertex deletion problem
- Linear‐time algorithms for eliminating claws in graphs
- Measuring indifference: unit interval vertex deletion
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- On the \(d\)-claw vertex deletion problem
This page was built for publication: Vertex deletion problems on chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786595)
