Distributed Connectivity Decomposition

We present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. As their primary applications, these decompositions allow us to achieve information flow with size close to the connectivity by parallelizing it along the trees. More specifically, our distributed decomposition algorithms are as follows: (I) A decomposition of each undirected graph with vertex-connectivity $k$ into (fractionally) vertex-disjoint weighted dominating trees with total weight $\Omega(\frac{k}{\log n})$, in $\widetilde{O}(D+\sqrt{n})$ rounds. (II) A decomposition of each undirected graph with edge-connectivity $\lambda$ into (fractionally) edge-disjoint weighted spanning trees with total weight $\lceil\frac{\lambda-1}{2}\rceil(1-\varepsilon)$, in $\widetilde{O}(D+\sqrt{n\lambda})$ rounds. We also show round complexity lower bounds of $\tilde{\Omega}(D+\sqrt{\frac{n}{k}})$ and $\tilde{\Omega}(D+\sqrt{\frac{n}{\lambda}})$ for the above two decompositions, using techniques of [Das Sarma et al., STOC'11]. Moreover, our vertex-connectivity decomposition extends to centralized algorithms and improves the time complexity of [Censor-Hillel et al., SODA'14] from $O(n^3)$ to near-optimal $\tilde{O}(m)$. As corollaries, we also get distributed oblivious routing broadcast with $O(1)$-competitive edge-congestion and $O(\log n)$-competitive vertex-congestion. Furthermore, the vertex connectivity decomposition leads to near-time-optimal $O(\log n)$-approximation of vertex connectivity: centralized $\widetilde{O}(m)$ and distributed $\tilde{O}(D+\sqrt{n})$. The former moves toward the 1974 conjecture of Aho, Hopcroft, and Ullman postulating an $O(m)$ centralized exact algorithm while the latter is the first distributed vertex connectivity approximation.


Similar Publications

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players Bob his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result it presents Bob with the next piece. This model has a closer and more natural correspondence to dynamic data structures than the classic communication models do and hence presents a new perspective on data structures. Read More


We revisit the range $\tau$-majority problem, which asks us to preprocess an array $A[1..n]$ for a fixed value of $\tau \in (0,1/2]$, such that for any query range $[i,j]$ we can return a position in $A$ of each distinct $\tau$-majority element. Read More


We study the problem of clustering sequences of unlabeled point sets taken from a common metric space. Such scenarios arise naturally in applications where a system or process is observed in distinct time intervals, such as biological surveys and contagious disease surveillance. In this more general setting existing algorithms for classical (i. Read More


In this paper, we examine the hash functions expressed as scalar products, i.e., $f(x)=$, for some bounded random vector $v$. Read More


Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of $1-\frac{1}{e}$ on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is $\frac{1}{1+1/e} \approx 0. Read More


We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic approach for solving mixed packing/covering integer programs in the online paradigm. In EW-DB-SF we are given an edge-weighted graph with a degree bound for every vertex. Read More


A sum where each of the $N$ summands can be independently chosen from two choices yields $2^N$ possible summation outcomes. There is an $\mathcal{O}(K^2)$-algorithm that finds the $K$ smallest/largest of these sums by evading the enumeration of all sums. Read More


We consider the problem of implementing a space-efficient dynamic trie, with an emphasis on good practical performance. For a trie with $n$ nodes with an alphabet of size $\sigma$, the information-theoretic lower bound is $n \log \sigma + O(n)$ bits. The Bonsai data structure is a compact trie proposed by Darragh et al. Read More


Suffix trees have recently become very successful data structures in handling large data sequences such as DNA or Protein sequences. Consequently parallel architectures have become ubiquitous. We present a novel alphabet-dependent parallel algorithm which attempts to take advantage of the perverseness of the multicore architecture. Read More


In this paper, we first remodel the line coverage as a 1D discrete problem with co-linear targets. Then, an order-based greedy algorithm, called OGA, is proposed to solve the problem optimally. It will be shown that the existing order in the 1D modeling, and especially the resulted Markov property of the selected sensors can help design greedy algorithms such as OGA. Read More