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

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
CountryIndia
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