Vertex deletion problems on chordal graphs

Yixin Cao, Yuping Ke, Yota Otachi, Jie You

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)75-86
Number of pages12
JournalTheoretical Computer Science
Publication statusPublished - 12 Oct 2018


  • (Unit) interval graph
  • Chordal graph
  • Hereditary property
  • Maximum (induced) subgraph
  • Split graph
  • Vertex deletion problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Vertex deletion problems on chordal graphs'. Together they form a unique fingerprint.

Cite this