Vertex deletion problems on chordal graphs

DOI10.4230/LIPICS.FSTTCS.2017.22MaRDI QIDQ5136314zbMATH OpenOpenAlexFDO

Authors Yixin Cao, Yuping Ke, Yota Otachi, Jie You

Publication date 25 November 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2017.22

zbMATH Keywords

(unit) interval graphchordal graphhereditary propertymaximum subgraphNP-completenesspolynomial-time algorithmsplit graphvertex deletion problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Vertex deletion problems on chordal graphs
• Chordal deletion is fixed-parameter tractable
• Chordal Deletion Is Fixed-Parameter Tractable
• Approximation and kernelization for chordal vertex deletion
• Approximation and kernelization for chordal vertex deletion

Cites work

• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• 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
• 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 1414279 (Why is no real title available?)
• 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
• New classes of perfect graphs
• 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
• Some simplified NP-complete graph problems
• The maximum k-colorable subgraph problem for chordal graphs
• The node-deletion problem for hereditary properties is NP-complete
• The Rectilinear Steiner Tree Problem is NP-Complete
• Trivially perfect graphs

Cited in

(8)

• Vertex deletion problems on chordal graphs
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• On the d-claw vertex deletion problem
• On some simplicial elimination schemes for chordal graphs
• Node-and edge-deletion NP-complete problems
• Vertex deletion on split graphs: beyond 4-hitting set
• Vertex deletion on split graphs: beyond 4-hitting set
• 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 Q5136314)