Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex Deletion
Ahn, Jungho; Kim, Eun Jung; Lee, Euiwoong (2022), Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex Deletion, Algorithmica, 84, 7, p. 2106-2133. 10.1007/s00453-022-00963-7
TypeArticle accepté pour publication ou publié
MetadataShow full item record
Department of Electrical Engineering [Korea Advanced Institute of Science and Technology] [KAIST]
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Electrical Engineering and Computer Science Department [Ann Arbor] [EECS]
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.
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é