Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
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.
- scientific article; zbMATH DE number 7765420
- Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems
- Cluster deletion on interval graphs and split related graphs
- Cluster deletion on interval graphs and split related graphs
- A polynomial kernel for distance-hereditary vertex deletion
- A polynomial kernel for distance-hereditary vertex deletion
- Vertex deletion problems on chordal graphs
- Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
- Vertex deletion problems on chordal graphs
- Hitting forbidden minors: approximation and kernelization
- A characterization of ptolemaic graphs
- A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
- A New Algorithm for Generating All the Maximal Independent Sets
- A polynomial kernel for distance-hereditary vertex deletion
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Approximation and kernelization for chordal vertex deletion
- Chordal deletion is fixed-parameter tractable
- Chordal editing is fixed-parameter tractable
- Compression via Matroids
- Computing the Minimum Fill-In is NP-Complete
- Constant factor approximation for subset feedback set problems via a new LP relaxation
- Erdős-Pósa property of chordless cycles and its applications
- Error compensation in leaf power problems
- Feedback vertex set inspired kernel for chordal vertex deletion
- Finding odd cycle transversals.
- Hitting diamonds and growing cacti
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- Interval deletion is fixed-parameter tractable
- Interval vertex deletion admits a polynomial kernel
- Laminar structure of ptolemaic graphs with applications
- Linear recognition of almost interval graphs
- Losing Treewidth by Separating Subsets
- On diameters and radii of bridged graphs
- Parameterized complexity of vertex deletion into perfect graph classes
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Rank-width and vertex-minors
- Structure and linear time recognition of 3-leaf powers
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Strong hardness of approximation for tree transversals
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems
- A polynomial kernel for distance-hereditary vertex deletion
- A constant-factor approximation for weighted bond cover
- Tight bounds for chordal/interval vertex deletion parameterized by treewidth
This page was built for publication: Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149107)
