Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistributed Approximation of Minimum $k$-edge-connected Spanning Subgraphs
135
0
0.0
(
0
)
Added by
Michal Dory
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Michal Dory
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph $G$ and an integer $r_{uv}$ for every pair of vertices $u,vin V(G)$. The objective is to construct a subgraph $H$ of minimum weight which contains $r_{uv}$ edge-disjoint (or node-disjoint) $u$-$v$ paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. In this paper, we consider the version of the problem where we are given a $lambda$-edge connected (di)graph $G$ with a non-negative weight function $w$ on the edges and an integer $k$, and the objective is to find a minimum weight spanning subgraph $H$ that is also $lambda$-edge connected, and has at least $k$ fewer edges than $G$. In other words, we are asked to compute a maximum weight subset of edges, of cardinality up to $k$, which may be safely deleted from $G$. Motivated by this question, we investigate the connectivity properties of $lambda$-edge connected (di)graphs and obtain algorithmically significant structural results. We demonstrate the importance of our structural results by presenting an algorithm running in time $2^{O(k log k)} |V(G)|^{O(1)}$ for $lambda$-ECS, thus proving its fixed-parameter tractability. We follow up on this result and obtain the {em first polynomial compression} for $lambda$-ECS on unweighted graphs. As a consequence, we also obtain the first fixed parameter tractable algorithm, and a polynomial kernel for a parameterized version of the classic Mininum Equivalent Graph problem. We believe that our structural results are of independent interest and will play a crucial role in the design of algorithms for connectivity-constrained problems in general and the SNDP problem in particular.
In 2009, Bang-Jensen asked whether there exists a function $g(k)$ such that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + g(k)$ arcs. In this paper, we answer the question by showing that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + 750k^2log(k+1)$ arcs.
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 cup 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{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+sqrt{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(h_{MST}+sqrt{n}log^{*}{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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
