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.
For the minimum weight 2-edge-connected spanning subgraph (2-ECSS) problem, there is a distributed algorithm of @cite_35 . Their approach is finding a specific spanning tree and then augmenting it to a 2-edge-connected graph. In the unweighted case, they augment a DFS tree following the sequential algorithm of Khuller and Vishkin @cite_32 , which results in an @math -round @math -approximation algorithm for 2-ECSS. In the weighted case they augment an MST and suggest a general @math -round 2-approximation algorithm for weighted TAP, which gives an @math -round @math -approximation algorithm for 2-ECSS. Our algorithms for TAP imply faster approximations for unweighted and weighted 2-ECSS.
@cite_35 @cite_32
1596370873 2541541317 2082227928 2047723482
We consider the distributed construction of a minimum weight 2- edge-connected spanning subgraph (2-ECSS) of a given weighted or unweighted graph. A 2-ECSS of a graph is a subgraph that, for each pair of vertices, contains at least two edge-disjoint paths connecting these vertices. The problem of finding a minimum weight 2-ECSS is NP-hard and a natural extension of the distributed MST construction problem, one of the most fundamental problems in the area of distributed computation. We present a distributed 3 2-approximation algorithm for the unweighted 2-ECSS construction problem that requires O(n) communication rounds and O(m) messages. Moreover, we present a distributed 3-approximation algorithm for the weighted 2-ECSS construction problem that requires O(nlogn) communication rounds and O(nlog2 n+m) messages. In the Tree Augmentation Problem (TAP) the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T+F is 2-edge-connected. The best approximation ratio known for TAP is 1.5. In the more general Weighted TAP problem, F should be of minimum weight. Weighted TAP admits several 2-approximation algorithms w.r.t. the standard cut-LP relaxation. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than 2 is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is an old open problem even for TAP. In this paper we introduce two different LP-relaxations, and for each of them give a simple algorithm that computes a feasible solution for TAP of size at most 7 4 times the optimal LP value. This gives some hope to break the ratio 2 for the weighted case. We present a probabilistic algorithm that, given a connected graph G (represented by adjacency lists) of average degree d, with edge weights in the set 1,...,w , and given a parameter @math , estimates in time @math the weight of the minimum spanning tree (MST) of G with a relative error of at most @math . Note that the running time does not depend on the number of vertices in G. We also prove a nearly matching lower bound of @math on the probe and time complexity of any approximation algorithm for MST weight. The essential component of our algorithm is a procedure for estimating in time @math the number of connected components of an unweighted graph to within an additive error of @math . (This becomes @math for @math .) The time bound is shown to be tight up to within the @math factor. Our connected-components algorithm picks @math vertices in the graph and then grows "local spanning trees" whose sizes are specified by a stochastic process. From the local information collected in this way, the algorithm is able to infer, with high confidence, an estimate of the number of connected components. We then show how estimates on the number of components in various subgraphs of G can be used to estimate the weight of its MST. Abstract In this paper we study the Steiner tree problem in graphs for the case when vertices as well as edges have weights associated with them. A greedy approximation algorithm based on “spider decompositions” was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximation ratio of 2 ln k , where k is the number of terminals. However, the best known lower bound on the approximation ratio is (1− o (1)) ln k , assuming that NP ⊈ DTIME [ n O (log log n ) ], by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of ln k . For the weighted case we develop a new decomposition theorem and generalize the notion of “spiders” to “branch-spiders” that are used to design a new algorithm with a worst case approximation factor of 1.5 ln k . We then generalize the method to yield an approximation factor of (1.35+ e ) ln k , for any constant e >0. These algorithms, although polynomial, are not very practical due to their high running time, since we need to repeatedly find many minimum weight matchings in each iteration. We also develop a simple greedy algorithm that is practical and has a worst case approximation factor of 1.6103 ln k . The techniques developed for this algorithm imply a method of approximating node weighted network design problems defined by 0–1 proper functions as well. These new ideas also lead to improved approximation guarantees for the problem of finding a minimum node weighted connected dominating set. The previous best approximation guarantee for this problem was 3 ln n by Guha and Khuller. By a direct application of the methods developed in this paper we are able to develop an algorithm with an approximation factor of (1.35+ e ) ln n for any fixed e >0.