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

DOI10.1007/S00453-022-00963-7zbMATH Open1502.68367arXiv2009.00809OpenAlexW3081965010MaRDI QIDQ2149107FDOQ2149107

Authors: Yanyan Li 

Publication date: 28 June 2022

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Finding odd cycle transversals.
• A New Algorithm for Generating All the Maximal Independent Sets
• Rank-width and vertex-minors
• On diameters and radii of bridged graphs
• Chordal editing is fixed-parameter tractable
• A characterization of ptolemaic graphs
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Chordal deletion is fixed-parameter tractable
• Error compensation in leaf power problems
• Interval deletion is fixed-parameter tractable
• Structure and linear time recognition of 3-leaf powers
• Parameterized complexity of vertex deletion into perfect graph classes
• Hitting diamonds and growing cacti
• Laminar structure of ptolemaic graphs with applications
• Linear recognition of almost interval graphs
• Compression via Matroids
• Approximation and kernelization for chordal vertex deletion
• Feedback vertex set inspired kernel for chordal vertex deletion
• Title not available (Why is that?)
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• Constant factor approximation for subset feedback set problems via a new LP relaxation
• A polynomial kernel for distance-hereditary vertex deletion
• Interval vertex deletion admits a polynomial kernel
• Losing Treewidth by Separating Subsets
• Erdős-Pósa property of chordless cycles and its applications
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems

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)