Vertex deletion problems on chordal graphs

DOI10.1016/J.TCS.2018.05.039zbMATH Open1401.68114arXiv1707.08690OpenAlexW2964176371MaRDI QIDQ1786595FDOQ1786595

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

Publication date: 24 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1707.08690

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

zbMATH Keywords

split graphhereditary propertychordal graphvertex deletion problem(unit) interval graphmaximum (induced) subgraph

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)

Cites Work

• Title not available (Why is that?)
• Fixed-parameter tractability of graph modification problems for hereditary properties
• The node-deletion problem for hereditary properties is NP-complete
• Title not available (Why is that?)
• On rigid circuit graphs
• Some simplified NP-complete graph problems
• Trivially perfect graphs
• HAMILTONian circuits in chordal bipartite graphs
• Large Induced Subgraphs via Triangulations and CMSO
• Node-Deletion Problems on Bipartite Graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Dominating sets for split and bipartite graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On the hardness of approximating minimization problems
• On the pathwidth of chordal graphs
• Chordal editing is fixed-parameter tractable
• Computing the Minimum Fill-In is NP-Complete
• Unit interval editing is fixed-parameter tractable
• Title not available (Why is that?)
• Largest chordal and interval subgraphs faster than \(2^n\)
• Chordal editing is fixed-parameter tractable
• On split-coloring problems
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• Approximate association via dissociation
• Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
• Measuring indifference: unit interval vertex deletion
• Linear recognition of almost interval graphs
• Exact algorithms via monotone local search
• Feedback vertex set inspired kernel for chordal vertex deletion
• Approximation and kernelization for chordal vertex deletion

Cited In (19)

• Vertex deletion on split graphs: beyond 4-hitting set
• \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
• Algorithms and complexity of \(s\)-club cluster vertex deletion
• Node-and edge-deletion NP-complete problems
• A tight approximation algorithm for the cluster vertex deletion problem
• Measuring indifference: unit interval vertex deletion
• \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Linear‐time algorithms for eliminating claws in graphs
• Proper Interval Vertex Deletion
• On some simplicial elimination schemes for chordal graphs
• Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
• Graph modification problem for some classes of graphs
• On the complexity of singly connected vertex deletion
• The vertex leafage of chordal graphs
• On the \(d\)-claw vertex deletion problem
• On the \(d\)-claw vertex deletion problem
• Algorithms for deletion problems on split graphs
• Deletion graph problems based on deadlock resolution

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)