×

Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. (English) Zbl 07693610

Summary: The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem (CAP) is arguably one of the most basic problems in this area: given a \(k\) (-edge)-connected graph \(G\) and a set of extra edges (links), select a minimum cardinality subset \(A\) of links such that adding \(A\) to \(G\) increases its edge connectivity to \(k+1\). Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and Jájá, SIAM J. Comput., 10 (1981), pp. 270-283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290-306] that CAP can be reduced to the case \(k=1\), also known as the tree augmentation problem (TAP) for odd \(k\), and to the case \(k=2\), also known as the cactus augmentation problem (CacAP) for even \(k\). Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC’20, ACM, New York, 2020, pp. 815-825], several better than 2 approximation algorithms were known for TAP, culminating with a recent \(1.458\) approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC’18, ACM, New York, 1918, pp. 632-645]. However, for CacAP the best known approximation was 2. In this paper we breach the 2 approximation barrier for CacAP, hence, for CAP, by presenting a polynomial-time \(2\ln (4)-\frac{967}{1120}+\varepsilon<1.91\) approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for TAP either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP ’14, Springer, Berlin, 2014, pp. 800-811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we “open the box” and exploit the specific properties of the instances of a Steiner tree arising from CacAP. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area.

MSC:

68W25 Approximation algorithms
05C85 Graph algorithms (graph-theoretic aspects)
05C40 Connectivity
Full Text: DOI

References:

[1] Adjiashvili, D., Beating approximation factor two for weighted tree augmentation with bounded costs, ACM Trans. Algorithms, 15 (2018), 19, doi:10.1145/3182395. · Zbl 1454.68085
[2] Angelidakis, H., Hyatt-Denesik, D., and Sanità, L., Node connectivity augmentation via iterative randomized rounding, Math. Program., to appear. · Zbl 07681270
[3] Basavaraju, M., Fomin, F. V., Golovach, P. A., Misra, P., Ramanujan, M. S., and Saurabh, S., Parameterized algorithms to preserve connectivity, in Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings, Part I, Copenhagen, Denmark, , Springer, Berlin, 2014, pp. 800-811, doi:10.1007/978-3-662-43948-7. · Zbl 1412.68078
[4] Byrka, J., Grandoni, F., and Jabal Ameli, A., Breaching the 2-approximation barrier for connectivity augmentation: A reduction to Steiner tree, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, , Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., and Chuzhoy, J., eds., ACM, New York, 2020, pp. 815-825. · Zbl 07298290
[5] Byrka, J., Grandoni, F., Rothvoß, T., and Sanità, L., Steiner tree approximation via iterative randomized rounding, J. ACM, 60 (2013), 6. · Zbl 1281.68234
[6] Cecchetto, F., Traub, V., and Zenklusen, R., 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, , ACM, New York, 2021, pp. 370-383, https://arxiv.org/abs/2012.00086. · Zbl 07765178
[7] Cheriyan, J. and Gao, Z., Approximating (unweighted) tree augmentation via lift-and-project, part I: Stemless TAP, Algorithmica, 80 (2018), pp. 530-559, doi:10.1007/s00453-016-0270-4. · Zbl 1395.90232
[8] Cheriyan, J. and Gao, Z., Approximating (unweighted) tree augmentation via lift-and-project, part II, Algorithmica, 80 (2018), pp. 608-651, doi:10.1007/s00453-017-0275-7. · Zbl 1395.90233
[9] Cheriyan, J., Jordán, T., and Ravi, R., On 2-coverings and 2-packings of laminar families, in Proceedings of Algorithms - ESA ’99, 7th Annual European Symposium, Prague, Czech Republic, , Springer, Berlin, 1999, pp. 510-520, doi:10.1007/3-540-48481-7_44. · Zbl 0945.05014
[10] Cheriyan, J. and Thurimella, R., Approximating minimum-size k-connected spanning subgraphs via matching, SIAM J. Comput., 30 (2000), pp. 528-560, doi:10.1137/S009753979833920X. · Zbl 1049.90104
[11] Cohen, N. and Nutov, Z., A (1+ln2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius, Theoret. Comput. Sci., 489-490 (2013), pp. 67-74, doi:10.1016/j.tcs.2013.04.004. · Zbl 1294.05146
[12] Dinitz, E. A., Karzanov, A. V., and Lomonosov, M. V., On the structure of a family of minimal weighted cuts in a graph, Studies in Discrete Optimization., Nauka, Moscow, 1976, pp. 290-306.
[13] Even, G., Feldman, J., Kortsarz, G., and Nutov, Z., A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2, ACM Trans. Algorithms, 5 (2009), 21. · Zbl 1398.68670
[14] Fiorini, S., Groß, M., Könemann, J., and Sanità, L., Approximating weighted tree augmentation via Chvátal-Gomory cuts, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, , Czumaj, A., ed., New Orleans, LA, SIAM, Philadelphia, 2018, pp. 817-831, doi:10.1137/1.9781611975031.53. · Zbl 1403.68347
[15] Frederickson, G. N. and JáJá, J., Approximation algorithms for several graph augmentation problems, SIAM J. Comput., 10 (1981), pp. 270-283. · Zbl 0461.05040
[16] Gabow, H. N. and Gallagher, S. R., Iterated rounding algorithms for the smallest k-edge connected spanning subgraph, SIAM J. Comput., 41 (2012), pp. 61-103, doi:10.1137/080732572. · Zbl 1243.68225
[17] Goemans, M. X., Goldberg, A. V., Plotkin, S. A., Shmoys, D., Tardos, É., and Williamson, D. P., Improved approximation algorithms for network design problems, in Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia, , SIAM, Philadelphia, 1994, pp. 223-232, doi:10.5555/314464.314497. · Zbl 0873.68005
[18] Grandoni, F., Jabal Ameli, A., and Traub, V., Breaching the 2-approximation barrier for the forest augmentation problem, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, , ACM, New York, 2022, pp. 1598-1611. · Zbl 07774441
[19] Grandoni, F., Kalaitzis, C., and Zenklusen, R., Improved approximation for tree augmentation: Saving by rewiring, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, , Los Angeles, CA, ACM, New York, 2018, pp. 632-645, doi:10.1145/3188745.3188898. · Zbl 1429.68190
[20] Gálvez, W., Grandoni, F., Jabal Ameli, A., and Sornat, K., On the cycle augmentation problem: Hardness and approximation algorithms, Theory Comput. Syst., 65 (2021), pp. 1-24, doi:10.1007/s00224-020-10025-6. · Zbl 1473.05292
[21] Hunkenschröder, C., Vempala, S. S., and Vetta, A., A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem, ACM Trans. Algorithms, 15 (2019), 55, doi:10.1145/3341599. · Zbl 1454.68184
[22] Iglesias, J. and Ravi, R., Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem, Oper. Res. Lett., 50 (2022), pp. 693-698. · Zbl 1525.90418
[23] Jain, K., A factor 2 approximation algorithm for the generalized Steiner network problem, Combinatorica, 21 (2001), pp. 39-60. · Zbl 1107.68533
[24] Khuller, S. and Thurimella, R., Approximation algorithms for graph augmentation, J. Algorithms, 14 (1993), pp. 214-225. · Zbl 0764.68120
[25] Klein, P. and Ravi, R., A nearly best-possible approximation algorithm for node-weighted steiner trees, J. Algorithms, 19 (1995), pp. 104-115. · Zbl 0836.68046
[26] Kortsarz, G. and Nutov, Z., Lp-relaxations for tree augmentation, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, 2016, Paris, France, , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany, 2016, 13, doi:10.4230/LIPIcs.APPROX-RANDOM.2016.13.
[27] Kortsarz, G. and Nutov, Z., A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2, ACM Trans. Algorithms, 12 (2016), 23. · Zbl 1398.68679
[28] Marx, D. and Végh, L. A., Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation, ACM Trans. Algorithms, 11 (2015), 27, doi:10.1145/2700210. · Zbl 1398.68255
[29] Nagamochi, H., An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree, Discrete Appl. Math., 126 (2003), pp. 83-113. · Zbl 1012.68226
[30] Nutov, Z., 2-node-connectivity network design, in Approximation and Online Algorithms - 18th International Workshop, WAOA 2020, Virtual Event, 2020, Revised Selected Papers, , Kaklamanis, C., and Levin, A., eds., , Springer, Cham, Switzerland, 2021, pp. 220-235, doi:10.1007/978-3-030-80879-2_15. · Zbl 07495129
[31] Nutov, Z., Approximation algorithms for connectivity augmentation problems, in Proceeding of International Computer Science Symposium in Russia, CSR 2021, Sochi, 2021, , pp. 321-338, https://link.springer.com/chapter/10.1007/978-3-030-79416-3_19. · Zbl 07493539
[32] Nutov, Z., On the tree augmentation problem, Algorithmica, 83 (2021), pp. 553-575, doi:10.1007/s00453-020-00765-9. · Zbl 1522.68417
[33] Robins, G. and Zelikovsky, A., Tighter bounds for graph Steiner tree approximation, SIAM J. Discrete Math., 19 (2005), pp. 122-134. · Zbl 1082.05088
[34] Sebö, A. and Vygen, J., Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs, Combinatorica, 34 (2014), pp. 597-629, http://arxiv.org/abs/1201.1870. · Zbl 1340.90201
[35] Traub, V. and Zenklusen, R., A better-than-2 approximation for weighted tree augmentation, in IEEE 62nd Annual IEEE Symposium on Foundations of Computer Science, , IEEE, Piscataway, NJ, 2021, pp. 1-12.
[36] Traub, V. and Zenklusen, R., Local search for weighted tree augmentation and Steiner tree, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, , SIAM, Philadelphia, pp. 3253-3271, doi:10.1137/1.9781611977073.128. · Zbl 07883709
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.