License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.22
URN: urn:nbn:de:0030-drops-83799
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8379/
Go to the corresponding LIPIcs Volume Portal

Cao, Yixin ; Ke, Yuping ; Otachi, Yota ; You, Jie

Vertex Deletion Problems on Chordal Graphs

pdf-format:
LIPIcs-FSTTCS-2017-22.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{cao_et_al:LIPIcs:2018:8379,
  author =	{Yixin Cao and Yuping Ke and Yota Otachi and Jie You},
  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 =	{Satya Lokam and R. Ramanujam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8379},
  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}
}

Keywords: vertex deletion problem, maximum subgraph, chordal graph, (unit) interval graph, split graph, hereditary property, NP-complete, polynomial-time algori
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI