Ahn, Jungho ;
Kim, Eun Jung ;
Lee, Euiwoong
Towards ConstantFactor Approximation for Chordal / DistanceHereditary 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 constantfactor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3leaf power graphs, and interval graphs are known to admit constantfactor approximation algorithms, but the question is open for chordal graphs and distancehereditary graphs.
In this paper, we add one more class to this list by presenting a constantfactor approximation algorithm when ℱ is the intersection of chordal graphs and distancehereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3leaf power graphs above. Our proof presents new properties and algorithmic results on interclique 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 ConstantFactor Approximation for Chordal / DistanceHereditary Vertex Deletion}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {62:162:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13406},
URN = {urn:nbn:de:0030drops134063},
doi = {10.4230/LIPIcs.ISAAC.2020.62},
annote = {Keywords: ptolemaic, approximation algorithm, linear programming, feedback vertex set}
}
04.12.2020
Keywords: 

ptolemaic, approximation algorithm, linear programming, feedback vertex set 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 