Abstract
We consider network design problems in which we are given a graph \(G=(V,E)\) with edge costs, and seek a min-cost/size 2-node-connected subgraph \(G'=(V',E')\) that satisfies a prescribed property.
-
In the Block-Tree Augmentation problem the goal is to augment a tree T by a min-size edge set \(F \subseteq E\) such that \(G'=T \cup F\) is 2-node-connected. We break the natural ratio of 2 for this problem and show that it admits approximation ratio 1.91. This result extends to the related Crossing Family Augmentation problem.
-
In the 2-Connected Dominating Set problem \(G'\) should dominate V. We give the first non-trivial approximation algorithm for this problem, with expected ratio \(\tilde{O}(\log ^4 |V|)\).
-
In the 2-Connected Quota Subgraph problem we are given node profits p(v) and \(G'\) should have profit at least a given quota Q. We show expected ratio \(\tilde{O}(\log ^2|V|)\), almost matching the best known ratio \(O(\log ^2|V|)\).
Our algorithms are very simple, and they combine three main ingredients:
-
1.
A probabilistic spanning tree embedding with distortion \(\tilde{O}(\log |V|)\) results in a variant of the Block-Tree Augmentation problem.
-
2.
An approximation ratio preserving reduction of Block-Tree Augmentation variants to Node Weighted Steiner Tree problems.
-
3.
Using existing approximation algorithms for variants of the Node Weighted Steiner Tree problem.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abraham, I., Bartal, Y., Neiman, O.: Nearly tight low stretch spanning trees. In: FOCS, pp. 781–790 (2008)
Adjiashvili, D.: Beating approximation factor two for weighted tree augmentation with bounded costs. In: SODA, pp. 2384–2399 (2017)
Basavaraju, M., Fomin, F.V., Golovach, P.A., Misra, P., Ramanujan, M.S., Saurabh, S.: Parameterized algorithms to preserve connectivity. ICALP, Part I, 800–811 (2014)
Bateni, M.H., Hajiaghayi, M.T., Liaghat, V.: Improved approximation algorithms for (budgeted) node-weighted Steiner problems. SIAM J. Comput. 47(4), 1275–1293 (2018)
Belgi, A., Nutov, Z.: An \(\tilde{O}(\log ^2 n)\)-approximation algorithm for \(2\)-edge-connected dominating set. CoRR abs/1912.09662 (2019). arxiv.org/abs/1912.09662
Byrka, J., Grandoni, F., Ameli, A.J.: Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. CoRR abs/1911.02259 (2019), arxiv.org/abs/1911.02259
Chekuri, C., Korula, N.: Pruning \(2\)-connected graphs. Algorithmica 62(1–2), 436–463 (2012)
Cheriyan, J., Jordán, T., Ravi, R.: On 2-coverings and 2-packing of laminar families. In: ESA, pp. 510–520 (1999)
Cheriyan, J., Karloff, H., Khandekar, R., Koenemann, J.: On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4), 399–401 (2008)
Cohen, N., Nutov, Z.: A \((1+\ln 2)\)-approximation algorithm for minimum-cost \(2\)-edge-connectivity augmentation of trees with constant radius. Theor. Comput. Sci. 489–490, 67–74 (2013)
Dai, F., Wu, J.: On constructing \(k\)-connected \(k\)-dominating set in wireless network. In: Parallel and Distributed Processing Symposium, p. 10 (2005)
Dinic, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of a family of minimal weighted cuts in a graph. Stud. Discrete Optim. 290–306 (1976)
Dinitz, Y., Nutov, Z.: A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance. In: STOC, pp. 509–518 (1995)
Elkin, M., Emek, Y., Spielman, D., Teng, S.H.: Lower-stretch spanning trees. SIAM J. Comput. 38(2), 608–628 (2008)
Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A \(1.8\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Trans. Algorithms 5(2) (2009)
Fiorini, S., Groß, M., Könemann, J., Sanitá, L.: A \(\frac{3}{2}\)-approximation algorithm for tree augmentation via chvátal-gomory cuts, 27 February 2017. https://arxiv.org/abs/1702.05567
Fleiner, T., Jordán, T.: Coverings and structure of crossing families. Math. Programm. 84(3), 505–518 (1999). https://doi.org/10.1007/s101070050035
Frederickson, G., Jájá, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10, 270–283 (1981)
Fukunaga, T.: Approximation algorithms for highly connected multi-dominating sets in unit disk graphs. Algorithmica 80(11), 3270–3292 (2018)
Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37, 66–84 (2002)
Grandoni, F., Kalaitzis, C., Zenklusen, R.: Improved approximation for tree augmentation: saving by rewiring. In: STOC, pp. 632–645 (2018)
Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998)
Guha, S., Khuller, S.: Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf. Comput. 150(1), 57–74 (1999)
Gupta, A., Krishnaswamy, R., Ravi, R.: Tree embeddings for two-edge-connected network design. In: SODA, pp. 1521–1538 (2010)
Khani, M., Salavatipour, M.: Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph. J. Comb. Optim. 31(2), 669–685 (2016)
Khuller, S.: Approximation algorithms for finding highly connected subgraphs. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, chap. 6, pp. 236–265. PWS (1995)
Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. J. Algorithms 14(2), 214–225 (1993)
Klein, P.N., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19(1), 104–115 (1995)
Könemann, J., Sadeghabad, S., Sanitá, L.: An LMP \(o(log n)\)-approximation algorithm for node weighted prize collecting Steiner tree. In: FOCS, pp. 568–577 (2013)
Kortsarz, G., Nutov, Z.: A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Trans. Algorithms 12(2), 23 (2016)
Maduel, Y., Nutov, Z.: Covering a laminar family by leaf to leaf links. Discrete Appl. Math. 158(13), 1424–1432 (2010)
Misra, P.: Parameterized Algorithms for Network Design. Ph.D. thesis, The Institute of Mathematical Sciences, Chennai (2016)
Nagamochi, H.: An approximation for finding a smallest \(2\)-edge connected subgraph containing a specified spanning tree. Discrete Appl. Math. 126, 83–113 (2003)
Nutov, Z.: Structures of Cuts and Cycles in Graphs; Algorithms and Applications. Ph.D. thesis, Technion, Israel Institute of Technology (1997)
Nutov, Z.: On the tree augmentation problem. In: ESA, pp. 61:1–61:14 (2017)
Nutov, Z.: Approximating \(k\)-connected \(m\)-dominating sets. CoRR abs/1902.03548 (2019). arxiv.org/abs/1902.03548
Wang, W., et al.: On construction of quality fault-tolerant virtual backbone in wireless networks. IEEE/ACM Trans. Netw. 21, 1499–1510 (2013)
Zhang, Z., Zhou, J., Mo, Y., Du, D.Z.: Approximation algorithm for minimum weight fault-tolerant virtual backbone in unit disk graphs. IEEE/ACM Trans. Netw. 25(2), 925–933 (2017)
Acknowledgment
I thank an anonymous referee for many useful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Nutov, Z. (2021). 2-Node-Connectivity Network Design. In: Kaklamanis, C., Levin, A. (eds) Approximation and Online Algorithms. WAOA 2020. Lecture Notes in Computer Science(), vol 12806. Springer, Cham. https://doi.org/10.1007/978-3-030-80879-2_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-80879-2_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-80878-5
Online ISBN: 978-3-030-80879-2
eBook Packages: Computer ScienceComputer Science (R0)