Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient Deterministic Distributed Coloring with Small Bandwidth
72
0
0.0
(
0
)
Added by
Yannic Maus
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show that the $(degree+1)$-list coloring problem can be solved deterministically in $O(D cdot log n cdotlog^2Delta)$ rounds in the CONGEST model, where $D$ is the diameter of the graph, $n$ the number of nodes, and $Delta$ the maximum degree. Using the recent polylogarithmic-time deterministic network decomposition algorithm by Rozhov{n} and Ghaffari [STOC 2020], this implies the first efficient (i.e., $polylog n$-time) deterministic CONGEST algorithm for the $(Delta+1)$-coloring and the $(mathit{degree}+1)$-list coloring problem. Previously the best known algorithm required $2^{O(sqrt{log n})}$ rounds and was not based on network decompositions. Our techniques also lead to deterministic $(mathit{degree}+1)$-list coloring algorithms for the congested clique and the massively parallel computation (MPC) model. For the congested clique, we obtain an algorithm with time complexity $O(logDeltacdotloglogDelta)$, for the MPC model, we obtain algorithms with round complexity $O(log^2Delta)$ for the linear-memory regime and $O(log^2Delta + log n)$ for the sublinear memory regime.
rate research
Read More
In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It was proved by Hasemann, Hirvonen, Rybicki and Suomela (2016) that for every real $alpha>1$ and integer $Delta$, a fractional coloring of total weight at most $alpha(Delta+1)$ can be obtained deterministically in a single round in graphs of maximum degree $Delta$, in the LOCAL model of computation. However, a major issue of this result is that the output of each vertex has unbounded size. Here we prove that even if we impose the more realistic assumption that the output of each vertex has constant size, we can find fractional colorings of total weight arbitrarily close to known tight bounds for the fractional chromatic number in several cases of interest. More precisely, we show that for any fixed $epsilon > 0$ and $Delta$, a fractional coloring of total weight at most $Delta+epsilon$ can be found in $O(log^*n)$ rounds in graphs of maximum degree $Delta$ with no $K_{Delta+1}$, while finding a fractional coloring of total weight at most $Delta$ in this case requires $Omega(log log n)$ rounds for randomized algorithms and $Omega( log n)$ rounds for deterministic algorithms. We also show how to obtain fractional colorings of total weight at most $2+epsilon$ in grids of any fixed dimension, for any $epsilon>0$, in $O(log^*n)$ rounds. Finally, we prove that in sparse graphs of large girth from any proper minor-closed family we can find a fractional coloring of total weight at most $2+epsilon$, for any $epsilon>0$, in $O(log n)$ rounds.
The problem of coloring the edges of an $n$-node graph of maximum degree $Delta$ with $2Delta - 1$ colors is one of the key symmetry breaking problems in the area of distributed graph algorithms. While there has been a lot of progress towards the understanding of this problem, the dependency of the running time on $Delta$ has been a long-standing open question. Very recently, Kuhn [SODA 20] showed that the problem can be solved in time $2^{O(sqrt{logDelta})}+O(log^* n)$. In this paper, we study the edge coloring problem in the distributed LOCAL model. We show that the $(mathit{degree}+1)$-list edge coloring problem, and thus also the $(2Delta-1)$-edge coloring problem, can be solved deterministically in time $log^{O(loglogDelta)}Delta + O(log^* n)$. This is a significant improvement over the result of Kuhn [SODA 20].
It was suggested that a programmable matter system (composed of multiple computationally weak mobile particles) should remain connected at all times since otherwise, reconnection is difficult and may be impossible. At the same time, it was not clear that allowing the system to disconnect carried a significant advantage in terms of time complexity. We demonstrate for a fundamental task, that of leader election, an algorithm where the system disconnects and then reconnects automatically in a non-trivial way (particles can move far away from their former neighbors and later reconnect to others). Moreover, the runtime of the temporarily disconnecting deterministic leader election algorithm is linear in the diameter. Hence, the disconnecting -- reconnecting algorithm is as fast as previous randomized algorithms. When comparing to previous deterministic algorithms, we note that some of the previous work assumed weaker schedulers. Still, the runtime of all the previous deterministic algorithms that did not assume special shapes of the particle system (shapes with no holes) was at least quadratic in $n$, where $n$ is the number of particles in the system. (Moreover, the new algorithm is even faster in some parameters than the deterministic algorithms that did assume special initial shapes.) Since leader election is an important module in algorithms for various other tasks, the presented algorithm can be useful for speeding up other algorithms under the assumption of a strong scheduler. This leaves open the question: can a deterministic algorithm be as fast as the randomized ones also under weaker schedulers?
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 give efficient randomized and deterministic distributed algorithms for computing a distance-$2$ vertex coloring of a graph $G$ in the CONGEST model. In particular, if $Delta$ is the maximum degree of $G$, we show that there is a randomized CONGEST model algorithm to compute a distance-$2$ coloring of $G$ with $Delta^2+1$ colors in $O(logDeltacdotlog n)$ rounds. Further if the number of colors is slightly increased to $(1+epsilon)Delta^2$ for some $epsilon>1/{rm polylog}(n)$, we show that it is even possible to compute a distance-$2$ coloring deterministically in polylog$(n)$ time in the CONGEST model. Finally, we give a $O(Delta^2 + log^* n)$-round deterministic CONGEST algorithm to compute distance-$2$ coloring with $Delta^2+1$ colors.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
