Abstract
Connectivity augmentation problems ask for adding a set of at most k edges whose insertion makes a given graph satisfy a specified connectivity property, such as bridge-connectivity or biconnectivity. We show that, for bridge-connectivity and biconnectivity, the respective connectivity augmentation problems admit problem kernels with O(k 2) vertices and links. Moreover, we study partial connectivity augmentation problems, naturally generalizing connectivity augmentation problems. Here, we do not require that, after adding the edges, the entire graph should satisfy the connectivity property, but a large subgraph. In this setting, two polynomial-time solvable connectivity augmentation problems behave differently, namely, the partial biconnectivity augmentation problem remains polynomial-time solvable whereas the partial strong connectivity augmentation problem becomes W[2]-hard with respect to k.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM Journal on Computing 5(4), 653–665 (1976)
Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM 2001 and APPROX 2001. LNCS, vol. 2129, pp. 90–101. Springer, Heidelberg (2001)
Frederickson, G.N., JáJá, J.: Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing 10(2), 270–283 (1981)
Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. Journal of Algorithms 14(2), 214–225 (1993)
Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of approximation for vertex-connectivity network design problems. SIAM Journal on Computing 33(3), 704–720 (2004)
Kortsarz, G., Nutov, Z.: A 12/7-approximation algorithm for the vertex-connectivity of a graph from 1 to 2, Manuscipt (2002)
Nagamochi, H.: An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree. Discrete Applied Mathematics 126, 83–113 (2003)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)
Rosenthal, A., Goldner, A.: Smallest augmentations to biconnect a graph. SIAM Journal on Computing 6(1), 55–66 (1977)
Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM Journal on Computing 1(2), 146–160 (1972)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guo, J., Uhlmann, J. (2007). Kernelization and Complexity Results for Connectivity Augmentation Problems. In: Dehne, F., Sack, JR., Zeh, N. (eds) Algorithms and Data Structures. WADS 2007. Lecture Notes in Computer Science, vol 4619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73951-7_42
Download citation
DOI: https://doi.org/10.1007/978-3-540-73951-7_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73948-7
Online ISBN: 978-3-540-73951-7
eBook Packages: Computer ScienceComputer Science (R0)