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.
Tree structures such as breadth-first search (BFS) trees and minimum spanning trees (MST) are among the most fundamental graph structures in distributed network algorithms. However, by definition, these structures are not robust against failures and even a single edge's removal can disrupt their functionality. A well-studied concept which attempts to circumvent this issue is Fault-Tolerant Tree Structures, where the tree gets augmented with additional edges from the network so that the functionality of the structure is maintained even when an edge fails. These structures, or other equivalent formulations, have been studied extensively from a centralized viewpoint. However, despite the fact that the main motivations come from distributed networks, their distributed construction has not been addressed before. In this paper, we present distributed algorithms for constructing fault tolerant BFS and MST structures. The time complexity of our algorithms are nearly optimal in the following strong sense: they almost match even the lower bounds of constructing (basic) BFS and MST trees.