Vertex Deletion Problems on Chordal Graphs

DOI10.4230/LIPICS.FSTTCS.2017.22zbMath1491.68084OpenAlexW2885933347MaRDI QIDQ5136314

Yota Otachi, Jie You, Yixin Cao, Yuping Ke

Publication date: 25 November 2020

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

zbMATH Keywords

split graphNP-completenesspolynomial-time algorithmchordal graphhereditary propertymaximum subgraphvertex deletion problem(unit) interval graph

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

On the \(d\)-claw vertex deletion problem ⋮ On the \(d\)-claw vertex deletion problem ⋮ Vertex deletion on split graphs: beyond 4-hitting set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chordal editing is fixed-parameter tractable
• Approximate association via dissociation
• Unit interval editing is fixed-parameter tractable
• On rigid circuit graphs
• Dominating sets for split and bipartite graphs
• On split-coloring problems
• New classes of perfect graphs
• The maximum k-colorable subgraph problem for chordal graphs
• The node-deletion problem for hereditary properties is NP-complete
• Some simplified NP-complete graph problems
• Trivially perfect graphs
• On the pathwidth of chordal graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• HAMILTONian circuits in chordal bipartite graphs
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• Largest Chordal and Interval Subgraphs Faster Than 2 n
• Large Induced Subgraphs via Triangulations and CMSO
• Chordal Editing is Fixed-Parameter Tractable
• Measuring Indifference: Unit Interval Vertex Deletion
• Node-Deletion Problems on Bipartite Graphs
• Computing the Minimum Fill-In is NP-Complete
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Linear Recognition of Almost Interval Graphs
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• Approximation and Kernelization for Chordal Vertex Deletion
• Exact Algorithms via Monotone Local Search
• On the hardness of approximating minimization problems
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: Vertex Deletion Problems on Chordal Graphs