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 language | English |
|---|---|
| Title of host publication | 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017 |
| Editors | Satya Lokam, R. Ramanujam |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Volume | 93 |
| ISBN (Electronic) | 9783959770552 |
| DOIs | |
| Publication status | Published - 1 Jan 2018 |
| Event | 37th 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 2017 → 14 Dec 2017 |
Conference
| Conference | 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017 |
|---|---|
| Country/Territory | India |
| City | Kanpur |
| Period | 12/12/17 → 14/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