Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/78143
Title: Vertex deletion problems on chordal graphs
Authors: Cao, Y 
Ke, Y 
Otachi, Y
You, J 
Keywords: (Unit) interval graph
Chordal graph
Hereditary property
Maximum subgraph
NP-complete
Polynomial-time algorithm
Split graph
Vertex deletion problem
Issue Date: 2018
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH
Source: Leibniz International Proceedings in Informatics, LIPIcs, v. 93, 22 How to cite?
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.
Description: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, KanpurKanpur, India, 12-14 Dec 2017
URI: http://hdl.handle.net/10397/78143
ISBN: 9783959770552
DOI: 10.4230/LIPIcs.FSTTCS.2017.22
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.