Document Open Access Logo

Fast Distributed Approximation for TAP and 2-Edge-Connectivity

Authors Keren Censor-Hillel, Michal Dory

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.21.pdf
  • Filesize: 0.62 MB
  • 20 pages

Document Identifiers

Author Details

Keren Censor-Hillel
Michal Dory

Cite As Get BibTex

Keren Censor-Hillel and Michal Dory. Fast Distributed Approximation for TAP and 2-Edge-Connectivity. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.21

Abstract

The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that T ∪ Aug is 2-edge-connected.
TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JáJá, SICOMP 1981. Recently, a 3/2-approximation was given for the unweighted case by Kortsarz and Nutov, TALG 2016, and recent breakthroughs by Adjiashvili, SODA 2017, and by Fiorini et al., 2017, give approximations better than 2 for bounded weights.
In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O(h) rounds, where h is the height of T . When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in O(D + (√n) log^{*} n) rounds, where n is the number of vertices and D is the diameter of G.
Immediate consequences of our results are an O(D)-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an O(hMST + (√n)log^{*} n)-round 3- approximation algorithm for the weighted case, where hMST is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augment- ing the connectivity of any connected spanning subgraph to 2.
Finally, we complement our study with proving lower bounds for distributed approximations of TAP.

Subject Classification

Keywords
  • approximation algorithms
  • distributed network design
  • connectivity augmentation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. David Adjiashvili. Beating approximation factor two for weighted tree augmentation with bounded costs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2384-2399. SIAM, 2017. Google Scholar
  2. Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. Nearest common ancestors: A survey and a new algorithm for a distributed environment. Theory of Computing Systems, 37(3):441-456, 2004. Google Scholar
  3. Keren Censor-Hillel and Michal Dory. Fast distributed approximation for TAP and 2-edge-connectivity. arXiv:1711.03359, 2017. URL: https://arxiv.org/abs/1711.03359.
  4. Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn. Distributed connectivity decomposition. In Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC), pages 156-165. ACM, 2014. Google Scholar
  5. Joseph Cheriyan and Zhihan Gao. Approximating (unweighted) tree augmentation via lift-and-project, part II. Algorithmica, pages 1-44, 2015. Google Scholar
  6. Michael Elkin. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM Journal on Computing, 36(2):433-456, 2006. Google Scholar
  7. Michael Elkin. A simple deterministic distributed MST algorithm, with near-optimal time and message complexities. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 157-163. ACM, 2017. URL: http://dx.doi.org/10.1145/3087801.3087823.
  8. Samuel Fiorini, Martin Groß, Jochen Könemann, and Laura Sanità. A 3/2-approximation algorithm for tree augmentation via chvátal-gomory cuts. CoRR, abs/1702.05567, 2017. URL: http://arxiv.org/abs/1702.05567.
  9. Greg N Frederickson and Joseph JáJá. Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing, 10(2):270-283, 1981. Google Scholar
  10. Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and systems (TOPLAS), 5(1):66-77, 1983. Google Scholar
  11. Juan A Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM Journal on Computing, 27(1):302-316, 1998. Google Scholar
  12. Mohsen Ghaffari and Merav Parter. Near-optimal distributed algorithms for fault-tolerant tree structures. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 387-396. ACM, 2016. Google Scholar
  13. Michel X Goemans, Andrew V Goldberg, Serge A Plotkin, David B Shmoys, Eva Tardos, and David P Williamson. Improved approximation algorithms for network design problems. In SODA, volume 94, pages 223-232, 1994. Google Scholar
  14. P Humblet. A distributed algorithm for minimum weight directed spanning trees. IEEE Transactions on Communications, 31(6):756-762, 1983. Google Scholar
  15. Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21(1):39-60, 2001. Google Scholar
  16. Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar. Efficient distributed approximation algorithms via probabilistic tree embeddings. Distributed Computing, 25(3):189-205, 2012. Google Scholar
  17. Samir Khuller. Approximation algorithms for finding highly connected subgraphs. In Approximation algorithms for NP-hard problems, pages 236-265. PWS Publishing Co., 1996. Google Scholar
  18. Samir Khuller and Ramakrishna Thurimella. Approximation algorithms for graph augmentation. Journal of Algorithms, 14(2):214-225, 1993. Google Scholar
  19. Samir Khuller and Uzi Vishkin. Biconnectivity approximations and graph carvings. Journal of the ACM (JACM), 41(2):214-235, 1994. Google Scholar
  20. Guy Kortsarz and Zeev Nutov. Approximating minimum cost connectivity problems. In Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2010. Google Scholar
  21. Guy Kortsarz and Zeev Nutov. A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Transactions on Algorithms (TALG), 12(2):23, 2016. Google Scholar
  22. Sven O Krumke, Peter Merz, Tim Nonner, and Katharina Rupp. Distributed approximation algorithms for finding 2-edge-connected subgraphs. In International Conference On Principles Of Distributed Systems (OPODIS), pages 159-173. Springer, 2007. Google Scholar
  23. Shay Kutten and David Peleg. Fast distributed construction of k-dominating sets and applications. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing (PODC), pages 238-251. ACM, 1995. Google Scholar
  24. Christoph Lenzen and Boaz Patt-Shamir. Improved distributed steiner forest construction. In Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC), pages 262-271. ACM, 2014. Google Scholar
  25. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. URL: http://dx.doi.org/10.1137/0221015.
  26. Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(1):583-596, 1992. Google Scholar
  27. Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms. In International Symposium on Distributed Computing, pages 439-453. Springer, 2014. Google Scholar
  28. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. A time-and message-optimal distributed algorithm for minimum spanning trees. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 743-756. ACM, 2017. Google Scholar
  29. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  30. David Pritchard. Robust network computation. Master’s thesis, MIT, 2005. Google Scholar
  31. David Pritchard and Ramakrishna Thurimella. Fast computation of small cuts via cycle space sampling. ACM Transactions on Algorithms (TALG), 7(4):46, 2011. Google Scholar
  32. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing, 41(5):1235-1265, 2012. Google Scholar
  33. Ramakrishna Thurimella. Sub-linear distributed algorithms for sparse certificates and biconnected components. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing (PODC), pages 28-37. ACM, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact