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

DOI10.1007/s00453-022-00963-7zbMath1502.68367arXiv2009.00809OpenAlexW3081965010MaRDI QIDQ2149107

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 algorithmdistance-hereditary graphschordal graphsfeedback vertex setPtolemaic graphs

Mathematics Subject Classification ID

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

Related Items (1)

Strong hardness of approximation for tree transversals

Cites Work

• Unnamed Item
• Unnamed Item
• Chordal editing is fixed-parameter tractable
• Parameterized complexity of vertex deletion into perfect graph classes
• Finding odd cycle transversals.
• Structure and linear time recognition of 3-leaf powers
• Chordal deletion is fixed-parameter tractable
• Laminar structure of ptolemaic graphs with applications
• On diameters and radii of bridged graphs
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Erdős-Pósa property of chordless cycles and its applications
• Error compensation in leaf power problems
• Rank-width and vertex-minors
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• Hitting Diamonds and Growing Cacti
• A characterization of ptolemaic graphs
• Computing the Minimum Fill-In is NP-Complete
• A New Algorithm for Generating All the Maximal Independent Sets
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation
• Linear Recognition of Almost Interval Graphs
• Approximation and Kernelization for Chordal Vertex Deletion
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• Compression via Matroids
• Interval Deletion Is Fixed-Parameter Tractable
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Interval Vertex Deletion Admits a Polynomial Kernel
• Losing Treewidth by Separating Subsets
• A polynomial kernel for distance-hereditary vertex deletion

This page was built for publication: Towards constant-factor approximation for chordal/distance-hereditary vertex deletion