Fast distributed approximation for TAP and 2-edge-connectivity

DOI10.1007/S00446-019-00353-3MaRDI QIDQ1988524zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, Michal Dory

Publication date 23 April 2020

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.03359, https://drops.dagstuhl.de/opus/volltexte/2018/8647/

zbMATH Keywords

approximation algorithmsconnectivity augmentationdistributed graph algorithmsdistributed network design

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40) Distributed algorithms (68W15)

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 $TcupAug$ 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 unweighted TAP by Kortsarz and Nutov, TALG 2016. Recent breakthroughs give an approximation of 1.458 for unweighted TAP [Grandoni et al., STOC 2018], and approximations better than 2 for bounded weights [Adjiashvili, SODA 2017; Fiorini et al., SODA 2018]. 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+sqrtnlo{g}^{\ast }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}+sqrtnlo{g}^{\ast }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.

Recommendations

• Fast distributed approximation for TAP and 2-edge-connectivity
• Brief announcement: Distributed approximation for tree augmentation
• LP-relaxations for tree augmentation
• A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Covering a laminar family by leaf to leaf links

Cites work

• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 6850362 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Almost-Tight Distributed Minimum Cut Algorithms
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Approximating (unweighted) tree augmentation via lift-and-project. II
• Approximating node connectivity problems via set covers
• Approximation Algorithms for Graph Augmentation
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation algorithms for NP-hard problems.
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• Biconnectivity approximations and graph carvings
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification and hardness of distributed approximation
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Fast computation of small cuts via cycle space sampling
• Fast distributed construction of k-dominating sets and applications
• Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
• Improved approximation for tree augmentation: saving by rewiring
• Improved distributed Steiner forest construction
• Locality in Distributed Graph Algorithms
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• On the distributional complexity of disjointness
• Small cuts and connectivity certificates: a fault tolerant approach
• Sub-linear distributed algorithms for sparse certificates and biconnected components

Cited in

(3)

• Brief announcement: Distributed approximation for tree augmentation
• Fast distributed approximation for TAP and 2-edge-connectivity
• Covering a laminar family by leaf to leaf links

This page was built for publication: Fast distributed approximation for TAP and 2-edge-connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1988524)