DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2017.22

Vertex Deletion Problems on Chordal Graphs

Authors: Yixin Cao, Yuping Ke, Yota Otachi, and Jie You

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

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.

Cite as

Yixin Cao, Yuping Ke, Yota Otachi, and Jie You. Vertex Deletion Problems on Chordal Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.FSTTCS.2017.22,
  author =	{Cao, Yixin and Ke, Yuping and Otachi, Yota and You, Jie},
  title =	{{Vertex Deletion Problems on Chordal Graphs}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.22},
  URN =		{urn:nbn:de:0030-drops-83799},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.22},
  annote =	{Keywords: vertex deletion problem, maximum subgraph, chordal graph, (unit) interval graph, split graph, hereditary property, NP-complete, polynomial-time algori}
}

Search Results

Documents authored by You, Jie

Vertex Deletion Problems on Chordal Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message