An efficient algorithm to add up-links to a rooted tree to obtain a minimum cost 2-connected graph
Resumo
We present an efficient algorithm to solve a special case of the following node-connectivity augmentation problem. Given a tree T = (V,E) and an additional set L ⊂ (V 2) of edges, called links, L ∩ E = ∅, each one with a rational nonnegative cost, find a minimum cost set of links F ⊆ L such that T + F is 2-connected. In general form, this problem is NP-hard. We focus on the up-link variation, where the tree T has a root, and every link is an edge from a node to its ancestor. We present a linear formulation for this problem together with a proof of integrality and an efficient combinatorial algorithm for it.
Referências
Adjiashvili, D. (2017). Beating approximation factor two for weighted tree augmentation with bounded costs. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 2384–2399. SIAM, Philadelphia, PA.
Angelidakis, H., Hyatt-Denesik, D., and Sanità, L. (2023). Node connectivity augmentation via iterative randomized rounding. Math. Program., 199(1-2):995–1031.
Bamas, E., Drygala, M., and Svensson, O. (2022). A simple LP-based approximation algorithm for the matching augmentation problem. In Proceedings of the 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022, volume 13265 of Lecture Notes in Comput. Sci., pages 57–69. Springer, Cham.
Cecchetto, F., Traub, V., and Zenklusen, R. (2021). Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. In Proceedings of the 53rd Annual ACM-SIGACT Symposium on Theory of Computing, STOC 2021, pages 370–383. ACM, New York.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to algorithms. MIT Press, Cambridge, MA, third edition.
Eswaran, K. P. and Tarjan, R. E. (1976). Augmentation problems. SIAM J. Comput., 5(4):653–665.
Frederickson, G. N. and Ja’Ja’, J. (1981). Approximation algorithms for several graph augmentation problems. SIAM J. Comput., 10(2):270–283.
Grout, Logan (2020). Augmenting trees to achieve 2-node-connectivity. Master’s thesis, University of Waterloo.
Nutov, Z. (2021). 2-node-connectivity network design. In Approximation and online algorithms, volume 12806 of Lecture Notes in Comput. Sci., pages 220–235. Springer, Cham.
Traub, V. and Zenklusen, R. (2021). A better-than-2 approximation for Weighted Tree Augmentation. In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 1–12. IEEE, Los Alamitos, CA.
Traub, V. and Zenklusen, R. (2022). Local search for weighted tree augmentation and Steiner Tree. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 3253–3271. SIAM, Philadelphia, PA.
Angelidakis, H., Hyatt-Denesik, D., and Sanità, L. (2023). Node connectivity augmentation via iterative randomized rounding. Math. Program., 199(1-2):995–1031.
Bamas, E., Drygala, M., and Svensson, O. (2022). A simple LP-based approximation algorithm for the matching augmentation problem. In Proceedings of the 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022, volume 13265 of Lecture Notes in Comput. Sci., pages 57–69. Springer, Cham.
Cecchetto, F., Traub, V., and Zenklusen, R. (2021). Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. In Proceedings of the 53rd Annual ACM-SIGACT Symposium on Theory of Computing, STOC 2021, pages 370–383. ACM, New York.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to algorithms. MIT Press, Cambridge, MA, third edition.
Eswaran, K. P. and Tarjan, R. E. (1976). Augmentation problems. SIAM J. Comput., 5(4):653–665.
Frederickson, G. N. and Ja’Ja’, J. (1981). Approximation algorithms for several graph augmentation problems. SIAM J. Comput., 10(2):270–283.
Grout, Logan (2020). Augmenting trees to achieve 2-node-connectivity. Master’s thesis, University of Waterloo.
Nutov, Z. (2021). 2-node-connectivity network design. In Approximation and online algorithms, volume 12806 of Lecture Notes in Comput. Sci., pages 220–235. Springer, Cham.
Traub, V. and Zenklusen, R. (2021). A better-than-2 approximation for Weighted Tree Augmentation. In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 1–12. IEEE, Los Alamitos, CA.
Traub, V. and Zenklusen, R. (2022). Local search for weighted tree augmentation and Steiner Tree. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 3253–3271. SIAM, Philadelphia, PA.
Publicado
21/07/2024
Como Citar
AZEVEDO, Gabriel Morete de; WAKABAYASHI, Yoshiko.
An efficient algorithm to add up-links to a rooted tree to obtain a minimum cost 2-connected graph. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 63-67.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.2500.
