اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDistributed Graph Coloring Made Easy
105
0
0.0
(
0
)
تأليف
Yannic Maus
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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$-col
oring 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].
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 mode
l, 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 g
eneral $(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.
In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-of
fs between the number of recolorings and the number of colors used. For any $d>0$, the first algorithm maintains a proper $O(mathcal{C} d N^{1/d})$-coloring while recoloring at most $O(d)$ vertices per update, where $mathcal{C}$ and $N$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $O(mathcal{C} d)$-coloring with $O(d N^{1/d})$ recolorings per update. The two converge when $d = log N$, maintaining an $O(mathcal{C} log N)$-coloring with $O(log N)$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices must recolor at least $Omega(N^frac{2}{c(c-1)})$ vertices per update, for any constant $c geq 2$.
Linials famous color reduction algorithm reduces a given $m$-coloring of a graph with maximum degree $Delta$ to a $O(Delta^2log m)$-coloring, in a single round in the LOCAL model. We show a similar result when nodes are restricted to choose their col
or from a list of allowed colors: given an $m$-coloring in a directed graph of maximum outdegree $beta$, if every node has a list of size $Omega(beta^2 (log beta+loglog m + log log |mathcal{C}|))$ from a color space $mathcal{C}$ then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linials color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring algorithm. As a corollary, we improve the state-of-the-art truly local $(deg+1)$-list coloring algorithm from Barenboim et al. [PODC18] by slightly reducing the runtime to $O(sqrt{DeltalogDelta})+log^* n$ and significantly reducing the message size (from huge to roughly $Delta$). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. [FOCS16].
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
