Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
183
0
0.0
(
0
)
Added by
Thatchaphol Saranurak
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
An $(epsilon,phi)$-expander decomposition of a graph $G=(V,E)$ is a clustering of the vertices $V=V_{1}cupcdotscup V_{x}$ such that (1) each cluster $V_{i}$ induces subgraph with conductance at least $phi$, and (2) the number of inter-cluster edges is at most $epsilon|E|$. In this paper, we give an improved distributed expander decomposition. Specifically, we construct an $(epsilon,phi)$-expander decomposition with $phi=(epsilon/log n)^{2^{O(k)}}$ in $O(n^{2/k}cdottext{poly}(1/phi,log n))$ rounds for any $epsilonin(0,1)$ and positive integer $k$. For example, a $(0.01,1/text{poly}log n)$-expander decomposition can be computed in $O(n^{gamma})$ rounds, for any arbitrarily small constant $gamma>0$. Previously, the algorithm by Chang, Pettie, and Zhang can construct a $(1/6,1/text{poly}log n)$-expander decomposition using $tilde{O}(n^{1-delta})$ rounds for any $delta>0$, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which forms a subgraph with arboricity at most $n^{delta}$. Our algorithm does not have this caveat. By slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC17], we obtain a triangle enumeration algorithm using $tilde{O}(n^{1/3})$ rounds. This matches the lower bound by Izumi and Le Gall [PODC17] and Pandurangan, Robinson and Scquizzato [SPAA18] of $tilde{Omega}(n^{1/3})$ which holds even in the CONGESTED CLIQUE model. This provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED CLIQUE. The key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.
rate research
Read More
We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in $tilde{O}(n^{1/2})$ rounds. In contrast, the previous state-of-the-art bounds for Triangle Detection and Enumeration were $tilde{O}(n^{2/3})$ and $tilde{O}(n^{3/4})$, respectively, due to Izumi and LeGall (PODC 2017). The main technical novelty in this work is a distributed graph partitioning algorithm. We show that in $tilde{O}(n^{1-delta})$ rounds we can partition the edge set of the network $G=(V,E)$ into three parts $E=E_mcup E_scup E_r$ such that (a) Each connected component induced by $E_m$ has minimum degree $Omega(n^delta)$ and conductance $Omega(1/text{poly} log(n))$. As a consequence the mixing time of a random walk within the component is $O(text{poly} log(n))$. (b) The subgraph induced by $E_s$ has arboricity at most $n^{delta}$. (c) $|E_r| leq |E|/6$. All of our algorithms are based on the following generic framework, which we believe is of interest beyond this work. Roughly, we deal with the set $E_s$ by an algorithm that is efficient for low-arboricity graphs, and deal with the set $E_r$ using recursive calls. For each connected component induced by $E_m$, we are able to simulate congested clique algorithms with small overhead by applying a routing algorithm due to Ghaffari, Kuhn, and Su (PODC 2017) for high conductance graphs.
Minimum-weight cut (min-cut) is a basic measure of a networks connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC13; Nanongkai, Su, DISC14]) can guarantee a solution that is $(1+epsilon)$-approximation at best while the exact $tilde O(n^{0.8}D^{0.2} + n^{0.9})$-time algorithm [Ghaffari, Nowicki, Thorup, SODA20] works only on *simple* networks (no weights and no parallel edges). Here $n$ and $D$ denote the networks number of vertices and hop-diameter, respectively. For the weighted case, the best bound was $tilde O(n)$ [Daga, Henzinger, Nanongkai, Saranurak, STOC19]. In this paper, we provide an *exact* $tilde O(sqrt n + D)$-time algorithm for computing min-cut on *weighted* networks. Our result improves even the previous algorithm that works only on simple networks. Its time complexity matches the known lower bound up to polylogarithmic factors. At the heart of our algorithm are a clever routing trick and two structural lemmas regarding the structure of a minimum cut of a graph. These two structural lemmas considerably strengthen and generalize the framework of Mukhopadhyay-Nanongkai [STOC20] and can be of independent interest.
Network decomposition is a central tool in distributed graph algorithms. We present two improvements on the state of the art for network decomposition, which thus lead to improvements in the (deterministic and randomized) complexity of several well-studied graph problems. - We provide a deterministic distributed network decomposition algorithm with $O(log^5 n)$ round complexity, using $O(log n)$-bit messages. This improves on the $O(log^7 n)$-round algorithm of Rozhov{n} and Ghaffari [STOC20], which used large messages, and their $O(log^8 n)$-round algorithm with $O(log n)$-bit messages. This directly leads to similar improvements for a wide range of deterministic and randomized distributed algorithms, whose solution relies on network decomposition, including the general distributed derandomization of Ghaffari, Kuhn, and Harris [FOCS18]. - One drawback of the algorithm of Rozhov{n} and Ghaffari, in the $mathsf{CONGEST}$ model, was its dependence on the length of the identifiers. Because of this, for instance, the algorithm could not be used in the shattering framework in the $mathsf{CONGEST}$ model. Thus, the state of the art randomized complexity of several problems in this model remained with an additive $2^{O(sqrt{loglog n})}$ term, which was a clear leftover of the older network decomposition complexity [Panconesi and Srinivasan STOC92]. We present a modified version that remedies this, constructing a decomposition whose quality does not depend on the identifiers, and thus improves the randomized round complexity for various problems.
We present a randomized distributed algorithm that computes a $Delta$-coloring in any non-complete graph with maximum degree $Delta geq 4$ in $O(log Delta) + 2^{O(sqrt{loglog n})}$ rounds, as well as a randomized algorithm that computes a $Delta$-coloring in $O((log log n)^2)$ rounds when $Delta in [3, O(1)]$. Both these algorithms improve on an $O(log^3 n/log Delta)$-round algorithm of Panconesi and Srinivasan~[STOC1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an $Omega(loglog n)$ round lower bound of Brandt et al.~[STOC16].
We present a simple deterministic distributed algorithm that computes a $(Delta+1)$-vertex coloring in $O(log^2 Delta cdot log n)$ rounds. The algorithm can be implemented with $O(log n)$-bit messages. The algorithm can also be extended to the more general $(degree+1)$-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for $(Delta+1)$-vertex coloring had remained a central open question in the area of distributed graph algorithms since the 1980s, until a recent network decomposition algorithm of Rozhov{n} and Ghaffari [STOC20]. The current state of the art is based on an improved variant of their decomposition, which leads to an $O(log^5 n)$-round algorithm for $(Delta+1)$-vertex coloring. Our coloring algorithm is completely different and considerably simpler and faster. It solves the coloring problem in a direct way, without using network decomposition, by gradually rounding a certain fractional color assignment until reaching an integral color assignments. Moreover, via the approach of Chang, Li, and Pettie [STOC18], this improved deterministic algorithm also leads to an improvement in the complexity of randomized algorithms for $(Delta+1)$-coloring, now reaching the bound of $O(log^3log n)$ rounds. As a further application, we also provide faster deterministic distributed algorithms for the following variants of the vertex coloring problem. In graphs of arboricity $a$, we show that a $(2+epsilon)a$-vertex coloring can be computed in $O(log^3 acdotlog n)$ rounds. We also show that for $Deltageq 3$, a $Delta$-coloring of a $Delta$-colorable graph $G$ can be computed in $O(log^2 Deltacdotlog^2 n)$ rounds.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
