Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
150
0
0.0
(
0
)
Added by
Michal Dory
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The minimum-weight $2$-edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of the well-studied minimum-weight spanning tree (MST) problem, and it has received considerable attention in the area of network design. The latter problem asks for a minimum-weight subgraph with an edge connectivity of $1$ between each pair of vertices while the former strengthens this edge-connectivity requirement to $2$. Despite this resemblance, the 2-ECSS problem is considerably more complex than MST. While MST admits a linear-time centralized exact algorithm, 2-ECSS is NP-hard and the best known centralized approximation algorithm for it (that runs in polynomial time) gives a $2$-approximation. In this paper, we give a deterministic distributed algorithm with round complexity of $widetilde{O}(D+sqrt{n})$ that computes a $(5+epsilon)$-approximation of 2-ECSS, for any constant $epsilon>0$. Up to logarithmic factors, this complexity matches the $widetilde{Omega}(D+sqrt{n})$ lower bound that can be derived from Das Sarma et al. [STOC11], as shown by Censor-Hillel and Dory [OPODIS17]. Our result is the first distributed constant approximation for 2-ECSS in the nearly optimal time and it improves on a recent randomized algorithm of Dory [PODC18], which achieved an $O(log n)$-approximation in $widetilde{O}(D+sqrt{n})$ rounds. We also present an alternative algorithm for $O(log n)$-approximation, whose round complexity is linear in the low-congestion shortcut parameter of the network, following a framework introduced by Ghaffari and Haeupler [SODA16]. This algorithm has round complexity $widetilde{O}(D+sqrt{n})$ in worst-case networks but it provably runs much faster in many well-behaved graph families of interest. For instance, it runs in $widetilde{O}(D)$ time in planar networks and those with bounded genus, bounded path-width or bounded tree-width.
rate research
Read More
In the minimum $k$-edge-connected spanning subgraph ($k$-ECSS) problem the goal is to find the minimum weight subgraph resistant to up to $k-1$ edge failures. This is a central problem in network design, and a natural generalization of the minimum spanning tree (MST) problem. While the MST problem has been studied extensively by the distributed computing community, for $k geq 2$ less is known in the distributed setting. In this paper, we present fast randomized distributed approximation algorithms for $k$-ECSS in the CONGEST model. Our first contribution is an $widetilde{O}(D + sqrt{n})$-round $O(log{n})$-approximation for 2-ECSS, for a graph with $n$ vertices and diameter $D$. The time complexity of our algorithm is almost tight and almost matches the time complexity of the MST problem. For larger constant values of $k$ we give an $widetilde{O}(n)$-round $O(log{n})$-approximation. Additionally, in the special case of unweighted 3-ECSS we show how to improve the time complexity to $O(D log^3{n})$ rounds. All our results significantly improve the time complexity of previous algorithms.
The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree $T$ for graph $G=(V,E)$ with $n$ vertices, such that the maximum degree $d$ of $T$ is the smallest among all spanning trees of $G$. In this paper, we present two new distributed approximation algorithms for the MDST problem. Our first result is a randomized distributed algorithm that constructs a spanning tree of maximum degree $hat d = O(dlog{n})$. It requires $O((D + sqrt{n}) log^2 n)$ rounds (w.h.p.), where $D$ is the graph diameter, which matches (within log factors) the optimal round complexity for the related minimum spanning tree problem. Our second result refines this approximation factor by constructing a tree with maximum degree $hat d = O(d + log{n})$, though at the cost of additional polylogarithmic factors in the round complexity. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990s, our results are first efficient distributed solutions for this problem.
This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with $n$ vertices and $m$ edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using $O(sqrt n)$ processors and $O(log n)$ worst-case update time, for a total of $O(sqrt n log n)$ work. This improves on the work of Ferragina [IPPS 1995] which costs $O(log n)$ worst-case update time and $O(n^{2/3} log{frac{m}{n}})$ work.
In the distributed subgraph-freeness problem, we are given a graph $H$, and asked to determine whether the network graph contains $H$ as a subgraph or not. Subgraph-freeness is an extremely local problem: if the network had no bandwidth constraints, we could detect any subgraph $H$ in $|H|$ rounds, by having each node of the network learn its entire $|H|$-neighborhood. However, when bandwidth is limited, the problem becomes harder. Upper and lower bounds in the presence of congestion have been established for several classes of subgraphs, including cycles, trees, and more complicated subgraphs. All bounds shown so far have been linear or sublinear. We show that the subgraph-freeness problem is not, in general, solvable in linear time: for any $k geq 2$, there exists a subgraph $H_k$ such that $H_k$-freeness requires $Omega( n^{2-1/k} / (Bk) )$ rounds to solve. Here $B$ is the bandwidth of each communication link. The lower bound holds even for diameter-3 subgraphs and diameter-3 network graphs. In particular, taking $k = Theta(log n)$, we obtain a lower bound of $Omega(n^2 / (B log n))$.
We give two fully dynamic algorithms that maintain a $(1+varepsilon)$-approximation of the weight $M$ of the minimum spanning forest of an $n$-node graph $G$ with edges weights in $[1,W]$, for any $varepsilon>0$. (1) Our deterministic algorithm takes $O({W^2 log W}/{varepsilon^3})$ worst-case update time, which is $O(1)$ if both $W$ and $varepsilon$ are constants. Note that there is a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006) shows that it takes $Omega(log n)$ time per operation to maintain the exact weight of the MSF that holds even in the unweighted case, i.e. for $W=1$. We further show that any deterministic data structure that dynamically maintains the $(1+varepsilon)$-approximate weight of the MSF requires super constant time per operation, if $Wgeq (log n)^{omega_n(1)}$. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case $O(frac{1}{varepsilon^4}log^3(frac{1}{varepsilon}))$ update time if $W$ is not too large, more specifically, if $W= O({(m^*)^{1/6}}/{log n})$, where $m^*$ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement this result by showing that for any constant $varepsilon,alpha>0$ and $W=n^{alpha}$, any (randomized) data structure that dynamically maintains the weight of the MSF of a graph $G$ with edge weights in $[1,W]$ and $W = Omega(varepsilon m^*)$ within a multiplicative factor of $(1+varepsilon)$ takes $Omega(log n)$ time per operation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
