Abstract
We consider the variant of the minimum vertex cover problem in which we require that the cover induces a connected subgraph. We give new approximation results for this problem in dense graphs, in which either the minimum or the average degree is linear. In particular, we prove tight parameterized upper bounds on the approximation returned by Savage’s algorithm, and extend a vertex cover algorithm from Karpinski and Zelikovsky to the connected case. The new algorithm approximates the minimum connected vertex cover problem within a factor strictly less than 2 on all dense graphs. All these results are shown to be tight. Finally, we introduce the price of connectivity for the vertex cover problem, defined as the worst-case ratio between the sizes of a minimum connected vertex cover and a minimum vertex cover. We prove that the price of connectivity is bounded by 2/(1 + ε) in graphs with average degree εn, and give a family of near-tight examples.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP complete. SIAM Journal of Applied Mathematics 32, 826–834 (1977)
Savage, C.D.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14(5), 233–237 (1982)
Fernau, H., Manlove, D.: Vertex and edge covers with clustering properties: Complexity and algorithms. In: Algorithms and Complexity in Durham 2006 - Proceedings of the Second ACiD Workshop, Durham, UK, 18-20 September 2006, pp. 69–84 (2006)
Escoffier, B., Gourvès, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem. In: Brandstädt, A., Kratsch, D., Müller, H. (eds.) WG 2007. LNCS, vol. 4769, pp. 202–213. Springer, Heidelberg (2007)
Fujito, T., Doi, T.: A 2-approximation NC algorithm for connected vertex cover and tree cover. Inf. Process. Lett. 90(2), 59–63 (2004)
Moser, H.: Exact algorithms for generalizations of vertex cover. Master’s thesis, Institut für Informatik, Friedrich-Schiller Universität Jena (2005)
Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41(3), 501–520 (2007)
Mölle, D., Richter, S., Rossmanith, P.: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Theory Comput. Syst. 43(2), 234–253 (2008)
Karpinski, M., Zelikovsky, A.: Approximating dense cases of covering problems. In: Pardalos, P., Du, D. (eds.) Proc. of the DIMACS Workshop on Network Design: Connectivity and Facilites Location. DIMACS series in Disc. Math. and Theor. Comp. Sci, vol. 40, pp. 169–178 (1997)
Ibaraki, T., Nagamochi, H.: An approximation of the minimum vertex cover in a graph. Japan J. Indust. Appl. Math. 16, 369–375 (1999)
Cardinal, J., Labbé, M., Langerman, S., Levy, E., Mélot, H.: A tight analysis of the maximal matching heuristic. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 701–709. Springer, Heidelberg (2005)
Imamura, T., Iwama, K.: Approximating vertex cover on dense graphs. In: Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 582–589 (2005)
Cardinal, J., Langerman, S., Levy, E.: Improved approximation bounds for edge dominating set in dense graphs. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol. 4368, pp. 108–120. Springer, Heidelberg (2007)
Karpinski, M.: Polynomial time approximation schemes for some dense instances of NP-hard optimization problems. Algorithmica 30(3), 386–397 (2001)
Bar-Yehuda, R., Kehat, Z.: Approximating the dense set-cover problem. J. Comput. Syst. Sci. 69(4), 547–561 (2004)
Paul, S., Miller, R.E.: Locating faults in a systematic manner in a large heterogeneous network. In: Proc. IEEE INFOCOM 1995, The Conference on Computer Communications. Fourteenth Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 522–529 (1995)
Grout, V.: Principles of cost minimisation in wireless networks. J. Heuristics 11(2), 115–133 (2005)
Wu, J., Lou, W., Dai, F.: Extended multipoint relays to determine connected dominating sets in MANETs. IEEE Trans. Computers 55(3), 334–347 (2006)
Thai, M.T., F.W.,, Liu, D., Zhu, S., Du, D.: Connected dominating sets in wireless networks with different transmission ranges. IEEE Trans. Mob. Comput 6(7), 721–730 (2007)
Mélot, H.: Facet Defining Inequalities among Graph Invariants: the system GraPHedron. Discrete Applied Mathematics (to appear, 2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cardinal, J., Levy, E. (2008). Connected Vertex Covers in Dense Graphs. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)