Vertex deletion problems on chordal graphs

Yixin Cao, Yuping Ke, Yota Otachi, Jie You

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

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.
Original languageEnglish
Title of host publication37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017
EditorsSatya Lokam, R. Ramanujam
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume93
ISBN (Electronic)9783959770552
DOIs
Publication statusPublished - 1 Jan 2018
Event37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017 - Indian Institute of Technology (IIT) Kanpur, Kanpur, India
Duration: 12 Dec 201714 Dec 2017

Conference

Conference37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017
Country/TerritoryIndia
CityKanpur
Period12/12/1714/12/17

Keywords

  • (unit) interval graph
  • Chordal graph
  • Hereditary property
  • Maximum subgraph
  • NP-complete
  • Polynomial-time algorithm
  • Split graph
  • Vertex deletion problem

ASJC Scopus subject areas

  • Software

Cite this