Towards constant-factor approximation for chordal/distance-hereditary vertex deletion (Q2149107): Difference between revisions

Given a vertex-weighted graph \(G = (V, E)\) and a family of graphs \(\mathcal{F}\), the Weighted \(\mathcal{F}\)-Deletion problem asks to find a subset of vertices \(S\subseteq V\) with minimum weight such that when vertices of \(S\) are deleted, the resulting graph \(G\setminus S\) belongs to \(\mathcal{F}\). Certain graph families, namely block graphs, 3-leaf power graphs, and interval graphs, are known to admit constant-factor approximation algorithms. The authors closely investigate two additional graph families: chordal graphs and distance-hereditary graphs. A \(O(\log^2 n)\)-approximation for chordal graphs and a \(O(\log^3 n)\)-approximation for distance-hereditary graphs were presented by \textit{A. Agrawal} et al. [LIPIcs -- Leibniz Int. Proc. Inform. 116, Article 1, 15 p. (2018; Zbl 1499.68395)], but even the existence of \(O(\log n)\)-factor approximation is not known for the family of chordal graphs. This paper presents a constant-factor approximation algorithm for the intersection of chordal and distance-hereditary graphs, known as Ptolemaic graphs. They are precisely the graphs without any induced \(C_{\ge4}\) or a gem, and they form a superclass of both 3-leaf power and block graphs. The 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.