Towards constant-factor approximation for chordal / distance-hereditary vertex deletion

09/02/2020
by   Jungho Ahn, et al.
0

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 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset