The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph @math and a spanning tree @math for it, and the goal is to augment @math with a minimum set of edges @math from @math , such that @math 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 ' a J ' a , 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 , 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 @math -approximation for weighted TAP which completes in @math rounds, where @math is the height of @math . When @math is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in @math rounds, where @math is the number of vertices and @math is the diameter of @math . Immediate consequences of our results are an @math -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 @math -round 3-approximation algorithm for the weighted case, where @math 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.
We consider the distributed construction of a minimum weight 2- edge-connected spanning subgraph (2-ECSS) of a given weighted or unweighted graph. A 2-ECSS of a graph is a subgraph that, for each pair of vertices, contains at least two edge-disjoint paths connecting these vertices. The problem of finding a minimum weight 2-ECSS is NP-hard and a natural extension of the distributed MST construction problem, one of the most fundamental problems in the area of distributed computation. We present a distributed 3 2-approximation algorithm for the unweighted 2-ECSS construction problem that requires O(n) communication rounds and O(m) messages. Moreover, we present a distributed 3-approximation algorithm for the weighted 2-ECSS construction problem that requires O(nlogn) communication rounds and O(nlog2 n+m) messages. A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not specified)? Unfortunately, the problem is known to be NP-hard. We consider the problem of finding a better approximation to the smallest 2-connected subgraph, by an efficient algorithm. For 2-edge connectivity, our algorithm guarantees a solution that is no more than 3 2 times the optimal. For 2-vertex connectivity, our algorithm guarantees a solution that is no more than 5 3 times the optimal. The previous best approximation factor is 2 for each of these problems. The new algorithms (and their analyses) depend upon a structure called a carving of a graph, which is of independent interest. We show that approximating the optimal solution to within an additive constant is NP-hard as well. We also consider the case where the graph has edge weights. For this case, we show that an approximation factor of 2 is possible in polynomial time for finding a k -edge connected spanning subgraph. This improves an approximation factor of 3 for k = 2, due to Frederickson and Ja´Ja´ [1981], and extends it for any k (with an increased running time though).