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 ∪ Aug is 2edgeconnected.
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/2approximation 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 2approximation 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 4approximation 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 2approximation algorithm for the minimum size 2edgeconnected 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 2edgeconnectivity 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.
BibTeX  Entry
@InProceedings{censorhillel_et_al:LIPIcs:2018:8647,
author = {Keren CensorHillel and Michal Dory},
title = {{Fast Distributed Approximation for TAP and 2EdgeConnectivity}},
booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
pages = {21:121:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770613},
ISSN = {18688969},
year = {2018},
volume = {95},
editor = {James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8647},
URN = {urn:nbn:de:0030drops86475},
doi = {10.4230/LIPIcs.OPODIS.2017.21},
annote = {Keywords: approximation algorithms, distributed network design, connectivity augmentation}
}
Keywords: 

approximation algorithms, distributed network design, connectivity augmentation 
Seminar: 

21st International Conference on Principles of Distributed Systems (OPODIS 2017) 
Issue Date: 

2018 
Date of publication: 

16.03.2018 