2026-07-26T03:15:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8647 2024-03-06T10:42:13Z ddc:004 open_access

Fast Distributed Approximation for TAP and 2-Edge-Connectivity Censor-Hillel, Keren Dory, Michal approximation algorithms distributed network design connectivity augmentation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keren Censor-Hillel and Michal Dory 2018 Is Part Of LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2017.21 urn:nbn:de:0030-drops-86475 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.21 eng https://creativecommons.org/licenses/by/3.0/legalcode