2017/07/27 by Yixin Cao, Cao, Yixin, Yuping Ke +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.1.3 #F.2.2 #FOS: Computer and information sciences #G.2.2 #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1707.08690
openalex publication_date 2017/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.