Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFully Dynamic $(Delta+1)$-Coloring in Constant Update Time
85
0
0.0
(
0
)
Added by
Quanquan C. Liu
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The problem of (vertex) $(Delta+1)$-coloring a graph of maximum degree $Delta$ has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA18, Bhattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized data structure for maintaining a $(Delta+1)$-coloring with $O(log Delta)$ expected amortized update time. In this paper, we present a $(Delta+1)$-coloring data structure that achieves a constant amortized update time and show that this time bound holds not only in expectation but also with high probability.
rate research
Read More
In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a $2-Omega(1)$ approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question. In this paper, we show that for any constant $epsilon > 0$, there is a randomized algorithm that with high probability maintains a $2-Omega(1)$ approximate maximum matching of a fully-dynamic general graph in worst-case update time $O(Delta^{epsilon}+text{polylog } n)$, where $Delta$ is the maximum degree. Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had $O(m^{1/4})$ update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time $O(n^epsilon)$ was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic time. Our algorithm is randomized and, per update, takes $O(log^2 Delta cdot log^2 n)$ expected time. Furthermore, the algorithm can be adjusted to have $O(log^2 Delta cdot log^4 n)$ worst-case update-time with high probability. Here, $n$ denotes the number of vertices and $Delta$ is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC18] who presented an algorithm with $O(m^{3/4})$ update-time (and thus broke the natural $Omega(m)$ barrier) where $m$ denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had $widetilde{O}(min{sqrt{n}, m^{1/3}})$ update-time [Assadi et al. SODA19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA19] states that in every $n$-vertex graph $G$ with maximum degree $Delta$, sampling $O(log{n})$ colors per each vertex independently from $Delta+1$ colors almost certainly allows for proper coloring of $G$ from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for $(Delta+1)$ coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we further study palette sparsification problems: * We prove that for $(1+varepsilon) Delta$ coloring, sampling only $O_{varepsilon}(sqrt{log{n}})$ colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors. * A natural family of graphs with chromatic number much smaller than $(Delta+1)$ are triangle-free graphs which are $O(frac{Delta}{ln{Delta}})$ colorable. We prove that sampling $O(Delta^{gamma} + sqrt{log{n}})$ colors per vertex is sufficient and necessary to obtain a proper $O_{gamma}(frac{Delta}{ln{Delta}})$ coloring of triangle-free graphs. * We show that sampling $O_{varepsilon}(log{n})$ colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of $(1+varepsilon) cdot deg(v)$ arbitrary colors, or even only $deg(v)+1$ colors when the lists are the sets ${1,ldots,deg(v)+1}$. Similar to previous work, our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.
We consider a decentralized graph coloring model where each vertex only knows its own color and whether some neighbor has the same color as it. The networking community has studied this model extensively due to its applications to channel selection, rate adaptation, etc. Here, we analyze variants of a simple algorithm of Bhartia et al. [Proc., ACM MOBIHOC, 2016]. In particular, we introduce a variant which requires only $O(nlogDelta)$ expected recolorings that generalizes the coupon collector problem. Finally, we show that the $O(nDelta)$ bound Bhartia et al. achieve for their algorithm still holds and is tight in adversarial scenarios.
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].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
