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.ISAAC.2020.62
URN: urn:nbn:de:0030-drops-134063
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13406/
Ahn, Jungho ;
Kim, Eun Jung ;
Lee, Euiwoong
Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion
Abstract
For a family of graphs ℱ, Weighted ℱ-Deletion is the problem for which the input is a vertex weighted graph G = (V, E) and the goal is to delete S ⊆ V with minimum weight such that G⧵S ∈ ℱ. Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs.
In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when ℱ is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of Feedback Vertex Set that exploits this relationship (named Feedback Vertex Set with Precedence Constraints), each of which may be of independent interest.
BibTeX - Entry
@InProceedings{ahn_et_al:LIPIcs:2020:13406,
author = {Jungho Ahn and Eun Jung Kim and Euiwoong Lee},
title = {{Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {62:1--62:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-173-3},
ISSN = {1868-8969},
year = {2020},
volume = {181},
editor = {Yixin Cao and Siu-Wing Cheng and Minming Li},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13406},
URN = {urn:nbn:de:0030-drops-134063},
doi = {10.4230/LIPIcs.ISAAC.2020.62},
annote = {Keywords: ptolemaic, approximation algorithm, linear programming, feedback vertex set}
}
|
Keywords: |
|
ptolemaic, approximation algorithm, linear programming, feedback vertex set |
|
Collection: |
|
31st International Symposium on Algorithms and Computation (ISAAC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
