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.
Similar content being viewed by others
References
Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: a unified framework for approximation algorithms. ACM Comput. Surv. 36(4), 422–463 (2004)
Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion, computer Science—theory and applications. Lecture Notes in Computer Science, vol. 8476, pp. 111–124. Springer (2014). ar**v:1306.3877
Cai, M., Deng, X., Zang, W.: An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput. 30(6), 1993–2007 (2001)
Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22(4), 111–118 (1998)
Fiorini, S., Joret, G., Schaudt, O.: Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol. 9682, pp. 238–249. Springer (2016)
Guruswami, V., Lee, E.: In Approximability of Feedback Vertex Set for Bounded Length Cycles, ECCC:TR14-006
Guruswami, V., Lee, E.: Inapproximability of \(H\)-transversal/packing. SIAM J. Discrete Math. 31(3), 1552–1571 (2017). ar**v:1506.06302
Hüffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst. 47(1), 196–217 (2010)
Iwata, Y., Oka, K.: Fast dynamic graph algorithms for parameterized problems, Algorithm theory—SWAT 2014. Lecture Notes in Computer Science, vol. 8503, pp. 241–252. Springer (2014)
Mnich, M., Williams, V.V., Végh, L.A.: A \(7/3\)-approximation for feedback vertex sets in tournaments. In: 24th Annual European Symposium on Algorithms, LIPIcs. Leibniz International Proceedings in Informatics, vol. 57, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2016). http://drops.dagstuhl.de/opus/volltexte/2016/6409, pp. Art. No. 67, 14
Tu, J., Zhou, W.: A primal-dual approximation algorithm for the vertex cover \({P}_3\) problem. Theor. Comput. Sci. 412(50), 7044–7048 (2011)
You, J., Wang, J., Cao, Y.: Approximate association via dissociation. Discrete Appl. Math. 219, 202–209 (2017). ar**v:1510.08276
Acknowledgements
We thank the anonymous referees for their careful reading of the paper and helpful remarks.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
S. Fiorini is supported by ERC Consolidator Grant 615640-ForEFront. G. Joret is supported by an ARC grant from the Wallonia-Brussels Federation of Belgium.
A preliminary version of this paper appeared as an extended abstract in the Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO ’16) [5].
Rights and permissions
About this article
Cite this article
Fiorini, S., Joret, G. & Schaudt, O. Improved approximation algorithms for hitting 3-vertex paths. Math. Program. 182, 355–367 (2020). https://doi.org/10.1007/s10107-019-01395-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-019-01395-y