Fast distributed approximation for TAP and 2-edge-connectivity
Keren Censor-Hillel, Michal Dory · Distributed Computing · 2019
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 \cup 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á (SIAM J Comput 10(2):270–283, 1981 ). Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov (ACM Trans Algorithms 12(2):23, 2016 ). Recent breakthroughs give an approximation of 1.458 for unweighted TAP (Grandoni et al. in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing (STOC 2018), 2018 ), and approximations better than 2 for bounded weights (Adjiashvili in: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms (SODA), 2017 ; Fiorini et al. in: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms (SODA 2018), New Orleans, LA, USA, 2018 . https://doi.org/10.1137/1.9781611975031.53 ). 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+\sqrt{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(h_{MST}+\sqrt{n}\log ^{*}{n})\) -round 3-approximation algorithm for the weighted case, where \(h_{MST}\) is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2. Finally, we complement our study with proving lower bounds for distributed approximations of TAP.