Title: Fast Distributed Approximation for TAP and 2-Edge-Connectivity,
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 \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á, 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+\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.