×

zbMATH — the first resource for mathematics

Improved approximation algorithms for hitting 3-vertex paths. (English) Zbl 1442.05222
Summary: 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, J. You et al. [Discrete Appl. Math. 219, 202–209 (2017; Zbl 1354.05110)] 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 V. Guruswami and E. Lee [SIAM J. Discrete Math. 31, No. 3, 1552–1571 (2017; Zbl 1371.68099)].

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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)
[2] 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). arXiv:1306.3877 · Zbl 1330.68220
[3] Cai, M.; Deng, X.; Zang, W., An approximation algorithm for feedback vertex sets in tournaments, SIAM J. Comput., 30, 6, 1993-2007 (2001) · Zbl 0980.68053
[4] Chudak, FA; Goemans, MX; Hochbaum, DS; Williamson, DP, 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) · Zbl 0920.90137
[5] Fiorini, S., Joret, G., Schaudt, O.: Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol. 9682, pp. 238-249. Springer (2016)
[6] Guruswami, V., Lee, E.: In Approximability of Feedback Vertex Set for Bounded Length Cycles, ECCC:TR14-006
[7] Guruswami, V., Lee, E.: Inapproximability of \(H\)-transversal/packing. SIAM J. Discrete Math. 31(3), 1552-1571 (2017). arXiv:1506.06302 · Zbl 1371.68099
[8] Hüffner, F.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Fixed-parameter algorithms for cluster vertex deletion, Theory Comput. Syst., 47, 1, 196-217 (2010) · Zbl 1205.68263
[9] 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) · Zbl 1416.68203
[10] 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 · Zbl 1397.68226
[11] Tu, J.; Zhou, W., A primal-dual approximation algorithm for the vertex cover \({P}_3\) problem, Theor. Comput. Sci., 412, 50, 7044-7048 (2011) · Zbl 1228.68033
[12] You, J., Wang, J., Cao, Y.: Approximate association via dissociation. Discrete Appl. Math. 219, 202-209 (2017). arXiv:1510.08276 · Zbl 1354.05110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.