License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2017.21
URN: urn:nbn:de:0030-drops-86475
Go to the corresponding LIPIcs Volume Portal

Censor-Hillel, Keren ; Dory, Michal

Fast Distributed Approximation for TAP and 2-Edge-Connectivity

LIPIcs-OPODIS-2017-21.pdf (0.6 MB)


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 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 + (√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(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 2-edge-connectivity 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

  author =	{Keren Censor-Hillel and Michal Dory},
  title =	{{Fast Distributed Approximation for TAP and 2-Edge-Connectivity}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-86475},
  doi =		{10.4230/LIPIcs.OPODIS.2017.21},
  annote =	{Keywords: approximation algorithms, distributed network design, connectivity augmentation}

Keywords: approximation algorithms, distributed network design, connectivity augmentation
Collection: 21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Issue Date: 2018
Date of publication: 28.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI