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

DOI10.1007/S00453-022-00963-7MaRDI QIDQ2149107zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 28 June 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.00809

zbMATH Keywords

linear programmingapproximation algorithmchordal graphsfeedback vertex setdistance-hereditary graphsPtolemaic graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Abstract: For a family of graphs $mathcalF$, Weighted $mathcalF$-Deletion is the problem for which the input is a vertex weighted graph $G=(V,E)$ and the goal is to delete $SsubseteqV$ with minimum weight such that $GsetminusSinmathcalF$. 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.

Recommendations

• 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

Cites work

• scientific article; zbMATH DE number 7559376 (Why is no real title available?)
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• A New Algorithm for Generating All the Maximal Independent Sets
• A characterization of ptolemaic graphs
• 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
• 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

Cited in

(7)

• Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• A polynomial kernel for distance-hereditary vertex deletion
• Strong hardness of approximation for tree transversals
• A constant-factor approximation for weighted bond cover

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)