Improved approximation algorithms for hitting 3-vertex paths
成果类型：
Article
署名作者：
Fiorini, Samuel; Joret, Gwenael; Schaudt, Oliver
署名单位：
Universite Libre de Bruxelles; Universite Libre de Bruxelles; University of Cologne
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-019-01395-y
发表日期：
2020
页码：
355-367
关键词：
摘要：
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 calledcluster vertex deletionin 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.