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. Very recently, You et al. [14] described an efficient 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 7/3-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 constrast 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 [7].
We acknowledge support from ERC grant FOREFRONT (grant agreement no. 615640) funded by the European Research Council under the EU’s 7th Framework Programme (FP7/2007-2013), and ARC grant AUWB-2012-12/17-ULB2 COPHYMA funded by the French community of Belgium.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Graphs in this paper are finite, simple, and undirected.
References
Bandelt, H.-J., Mulder, H.M.: Distance-hereditary graphs. J. Comb. Theory Ser. B 41(2), 182–208 (1986)
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)
Anudhyan, B., Marek, C., Tomasz, K., Marcin, P.: A fast branching algorithm for cluster vertex deletion. In: Hirsch, Edward A., Kuznetsov, Sergei O., Pin, Jean-Éric, Vereshchagin, Nikolay K. (eds.) CSR 2014. LNCS, vol. 8476, pp. 111–124. Springer, Heidelberg (2014). ar**v:1306.3877
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)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2010)
Guruswami, V., Lee, E.: Inapproximability of feedback vertex set for bounded length cycles. ECCC:TR14-006
Guruswami, V., Lee, E.: Inapproximability of \(H\)-transversal/packing. ar**v:1506.06302
Hüffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theor. Comput. Syst. 47(1), 196–217 (2010)
Iwata, Y., Oka, K.: Fast dynamic graph algorithms for parameterized problems. In: Ravi, R., Gørtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 241–252. Springer, Heidelberg (2014)
Kloks, T., Kratsch, D., Müller, H.: Dominoes. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 106–120. Springer, Heidelberg (1995)
Mnich, M., Williams, V.V., Végh, L.A.: A \(7, 3\)-approximation for feedback vertex sets in tournaments. ar**v:1511.01137
Jianhua, T., Zhou, W.: A primal-dual approximation algorithm for the vertex cover \({P}_3\) problem. Theoret. Comput. Sci. 412(50), 7044–7048 (2011)
You, J., Wang, J., Cao, Y.: Approximate association via dissociation. ar**v:1510.08276
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Fiorini, S., Joret, G., Schaudt, O. (2016). Improved Approximation Algorithms for Hitting 3-Vertex Paths. In: Louveaux, Q., Skutella, M. (eds) Integer Programming and Combinatorial Optimization. IPCO 2016. Lecture Notes in Computer Science(), vol 9682. Springer, Cham. https://doi.org/10.1007/978-3-319-33461-5_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-33461-5_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-33460-8
Online ISBN: 978-3-319-33461-5
eBook Packages: Computer ScienceComputer Science (R0)