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

NP-completenesssplit graphpolynomial-time algorithmhereditary propertychordal graphmaximum subgraphvertex deletion problem(unit) interval graph

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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 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

(8)

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