Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Distributed $Delta$-Coloring
93
0
0.0
(
0
)
Added by
Yannic Maus
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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].
rate research
Read More
In this paper we present a deterministic CONGEST algorithm to compute an $O(kDelta)$-vertex coloring in $O(Delta/k)+log^* n$ rounds, where $Delta$ is the maximum degree of the network graph and $1leq kleq O(Delta)$ can be freely chosen. The algorithm is extremely simple: Each node locally computes a sequence of colors and then it tries colors from the sequence in batches of size $k$. Our algorithm subsumes many important results in the history of distributed graph coloring as special cases, including Linials color reduction [Linial, FOCS87], the celebrated locally iterative algorithm from [Barenboim, Elkin, Goldenberg, PODC18], and various algorithms to compute defective and arbdefective colorings. Our algorithm can smoothly scale between these and also simplifies the state of the art $(Delta+1)$-coloring algorithm. At the cost of losing the full algorithms simplicity we also provide a $O(kDelta)$-coloring algorithm in $O(sqrt{Delta/k})+log^* n$ rounds. We also provide improved deterministic algorithms for ruling sets, and, additionally, we provide a tight characterization for one-round color reduction algorithms.
Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an $n$-node graph $G$, and where the nodes of $G$ operate in synchronous communication rounds in which they can exchange $O(log n)$-bit messages over all the edges of $G$. For graphs with maximum degree $Delta$, we show that the $(Delta+1)$-list coloring problem (and therefore also the standard $(Delta+1)$-coloring problem) can be solved in $O(log^5log n)$ rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous $(Delta+1)$-coloring algorithm in the CONGEST model had a running time of $O(logDelta + log^6log n)$ rounds. As a function of $n$ alone, the best previous algorithm therefore had a round complexity of $O(log n)$, which is a bound that can also be achieved by a na{i}ve folklore algorithm. For large maximum degree $Delta$, our algorithm hence is an exponential improvement over the previous state of the art.
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.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
