2026-08-03T09:42:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13406 2024-03-06T10:51:54Z ddc:004 open_access

Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion Ahn, Jungho Kim, Eun Jung Lee, Euiwoong ptolemaic approximation algorithm linear programming feedback vertex set 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jungho Ahn and Eun Jung Kim and Euiwoong Lee 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.62 urn:nbn:de:0030-drops-134063 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.62 eng https://creativecommons.org/licenses/by/3.0/legalcode