Publication:2191773

DOI10.1007/978-3-319-33461-5_20zbMath1442.05222arXiv1808.10370OpenAlexW2941863476WikidataQ128007423 ScholiaQ128007423MaRDI QIDQ2191773

Oliver Schaudt, Samuel Fiorini, Gwenaël Joret

Publication date: 26 June 2020

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Abstract: We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. This problem is often called cluster vertex deletion in the literature and admits a straightforward 3-approximation algorithm since it is a special case of the vertex cover problem on a 3-uniform hypergraph. Recently, You, Wang, and Cao described an efficient 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 9/4-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp contrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Lee.

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

zbMATH Keywords

cluster vertex deletion

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Approximate association via dissociation
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Fixed-parameter algorithms for cluster vertex deletion
• Distance-hereditary graphs
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Improved approximation algorithms for hitting 3-vertex paths
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• Fast Dynamic Graph Algorithms for Parameterized Problems
• A 7/3-Approximation for Feedback Vertex Sets in Tournaments
• A Fast Branching Algorithm for Cluster Vertex Deletion
• Inapproximability of $H$-Transversal/Packing

Related Items (10)

The maximum independent union of cliques problem: complexity and exact approaches ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Improved approximation algorithms for hitting 3-vertex paths ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Approximate association via dissociation ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ On the \(d\)-claw vertex deletion problem ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Approximation algorithms for hitting subgraphs

This page was built for publication: Improved approximation algorithms for hitting 3-vertex paths