Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
Ahn, Jungho; Kim, Eun Jung; Lee, Euiwoong (2020), Towards constant-factor approximation for chordal / distance-hereditary vertex deletion, in Cao, Yixin; Cheng, Siu-Wing; Li, Minming, 31st International Symposium on Algorithms and Computation (ISAAC 2020), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, p. 62:1–62:16. 10.4230/LIPIcs.ISAAC.2020.62
TypeCommunication / Conférence
Conference title31st International Symposium on Algorithms and Computation (ISAAC 2020)
Conference cityHong Kong
Book title31st International Symposium on Algorithms and Computation (ISAAC 2020)
Book authorCao, Yixin; Cheng, Siu-Wing; Li, Minming
MetadataShow full item record
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)For a family of graphs F, Weighted F-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∈F. 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 F 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.
Subjects / Keywordsptolemaic; approximation algorithm; linear programming; feedback vertexset
Showing items related by title and author.
Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, O-joung; Paul, Christophe (2017) Article accepté pour publication ou publié