Skip to main content
Springer Nature Link
Log in

2-Node-Connectivity Network Design

  • Conference paper
  • First Online:
Approximation and Online Algorithms (WAOA 2020)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12806))

Included in the following conference series:

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. 1.

    A probabilistic spanning tree embedding with distortion \(\tilde{O}(\log |V|)\) results in a variant of the Block-Tree Augmentation problem.

  2. 2.

    An approximation ratio preserving reduction of Block-Tree Augmentation variants to Node Weighted Steiner Tree problems.

  3. 3.

    Using existing approximation algorithms for variants of the Node Weighted Steiner Tree problem.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 139.00
Price excludes VAT (USA)
Softcover Book
USD 179.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Abraham, I., Bartal, Y., Neiman, O.: Nearly tight low stretch spanning trees. In: FOCS, pp. 781–790 (2008)

    Google Scholar 

  2. Adjiashvili, D.: Beating approximation factor two for weighted tree augmentation with bounded costs. In: SODA, pp. 2384–2399 (2017)

    Google Scholar 

  3. 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)

    Google Scholar 

  4. 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)

    Article  MathSciNet  Google Scholar 

  5. 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

  6. 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

  7. Chekuri, C., Korula, N.: Pruning \(2\)-connected graphs. Algorithmica 62(1–2), 436–463 (2012)

    Article  MathSciNet  Google Scholar 

  8. Cheriyan, J., Jordán, T., Ravi, R.: On 2-coverings and 2-packing of laminar families. In: ESA, pp. 510–520 (1999)

    Google Scholar 

  9. Cheriyan, J., Karloff, H., Khandekar, R., Koenemann, J.: On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4), 399–401 (2008)

    Article  MathSciNet  Google Scholar 

  10. 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)

    Article  Google Scholar 

  11. Dai, F., Wu, J.: On constructing \(k\)-connected \(k\)-dominating set in wireless network. In: Parallel and Distributed Processing Symposium, p. 10 (2005)

    Google Scholar 

  12. 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)

    Google Scholar 

  13. 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)

    Google Scholar 

  14. Elkin, M., Emek, Y., Spielman, D., Teng, S.H.: Lower-stretch spanning trees. SIAM J. Comput. 38(2), 608–628 (2008)

    Article  MathSciNet  Google Scholar 

  15. 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)

    Google Scholar 

  16. 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

  17. Fleiner, T., Jordán, T.: Coverings and structure of crossing families. Math. Programm. 84(3), 505–518 (1999). https://doi.org/10.1007/s101070050035

  18. Frederickson, G., Jájá, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10, 270–283 (1981)

    Article  MathSciNet  Google Scholar 

  19. Fukunaga, T.: Approximation algorithms for highly connected multi-dominating sets in unit disk graphs. Algorithmica 80(11), 3270–3292 (2018)

    Article  MathSciNet  Google Scholar 

  20. Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37, 66–84 (2002)

    Article  MathSciNet  Google Scholar 

  21. Grandoni, F., Kalaitzis, C., Zenklusen, R.: Improved approximation for tree augmentation: saving by rewiring. In: STOC, pp. 632–645 (2018)

    Google Scholar 

  22. Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998)

    Article  MathSciNet  Google Scholar 

  23. Guha, S., Khuller, S.: Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf. Comput. 150(1), 57–74 (1999)

    Article  MathSciNet  Google Scholar 

  24. Gupta, A., Krishnaswamy, R., Ravi, R.: Tree embeddings for two-edge-connected network design. In: SODA, pp. 1521–1538 (2010)

    Google Scholar 

  25. 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)

    Article  MathSciNet  Google Scholar 

  26. 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)

    Google Scholar 

  27. Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. J. Algorithms 14(2), 214–225 (1993)

    Article  MathSciNet  Google Scholar 

  28. Klein, P.N., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19(1), 104–115 (1995)

    Article  MathSciNet  Google Scholar 

  29. 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)

    Google Scholar 

  30. 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)

    Google Scholar 

  31. Maduel, Y., Nutov, Z.: Covering a laminar family by leaf to leaf links. Discrete Appl. Math. 158(13), 1424–1432 (2010)

    Article  MathSciNet  Google Scholar 

  32. Misra, P.: Parameterized Algorithms for Network Design. Ph.D. thesis, The Institute of Mathematical Sciences, Chennai (2016)

    Google Scholar 

  33. Nagamochi, H.: An approximation for finding a smallest \(2\)-edge connected subgraph containing a specified spanning tree. Discrete Appl. Math. 126, 83–113 (2003)

    Article  MathSciNet  Google Scholar 

  34. Nutov, Z.: Structures of Cuts and Cycles in Graphs; Algorithms and Applications. Ph.D. thesis, Technion, Israel Institute of Technology (1997)

    Google Scholar 

  35. Nutov, Z.: On the tree augmentation problem. In: ESA, pp. 61:1–61:14 (2017)

    Google Scholar 

  36. Nutov, Z.: Approximating \(k\)-connected \(m\)-dominating sets. CoRR abs/1902.03548 (2019). arxiv.org/abs/1902.03548

  37. Wang, W., et al.: On construction of quality fault-tolerant virtual backbone in wireless networks. IEEE/ACM Trans. Netw. 21, 1499–1510 (2013)

    Google Scholar 

  38. 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)

    Article  Google Scholar 

Download references

Acknowledgment

I thank an anonymous referee for many useful comments.

Author information

Authors and Affiliations

  1. The Open University of Israel, Ra’anana, Israel

    Zeev Nutov

Authors
  1. Zeev Nutov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zeev Nutov .

Editor information

Editors and Affiliations

  1. Computer Technology Institute, University of Patras, Patras, Greece

    Christos Kaklamanis

  2. Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa, Israel

    Asaf Levin

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics

Search

Navigation