An optimal distributed (+1)-coloring algorithm?

DOI10.1145/3188745.3188964MaRDI QIDQ5230309zbMATH OpenOpenAlexWikidataFDO

Authors Yi-Jun Chang, Wenzheng Li, Seth Pettie

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.01361

zbMATH Keywords

distributed algorithmslocal modelvertex coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Abstract: Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for $(Delta+1)$-list coloring in the randomized $sfLOCAL$ model running in $O(mathsf{Det}_{scriptscriptstyled}(extpolylogn))$ time, where $mathsf{Det}_{scriptscriptstyled}(n^{\prime })$ is the deterministic complexity of $(extdeg+1)$-list coloring on $n^{\prime }$-vertex graphs. (In this problem, each $v$ has a palette of size $extdeg(v)+1$.) This improves upon a previous randomized algorithm of Harris, Schneider, and Su [STOC'16, JACM'18] with complexity $O(sqrtlogDelta+loglogn+mathsf{Det}_{scriptscriptstyled}(extpolylogn))$, and, for some range of $Delta$, is much faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [FOCS'16] and Barenboim, Elkin, and Goldenberg [PODC'18], with complexity $O(sqrtDeltalogDeltalo{g}^{a}stDelta+lo{g}^{\ast }n)$. Our algorithm "appears to be" optimal, in view of the $Omega(mathsfDet(extpolylogn))$ randomized lower bound due to Chang, Kopelowitz, and Pettie [FOCS'16], where $mathsfDet$ is the deterministic complexity of $(Delta+1)$-list coloring. At present, the best upper bounds on $mathsf{Det}_{scriptscriptstyled}(n^{\prime })$ and $mathsfDet(n^{\prime })$ are both $2^{O(sqrtlog{n}^{\prime })}$ and use a black box application of network decompositions (Panconesi and Srinivasan [Journal of Algorithms'96]). It is quite possible that the true complexities of both problems are the same, asymptotically, which would imply the randomized optimality of our $(Delta+1)$-list coloring algorithm.

Recommendations

• Distributed (+1)-coloring via ultrafast graph shattering
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Improved distributed \(\Delta\)-coloring
• Improved distributed delta-coloring

Cited in

(37)

• Improved distributed \(\Delta\)-coloring
• Linial for lists
• Distributed coloring in sparse graphs with fewer colors
• Distributed minimum vertex coloring and maximum independent set in chordal graphs
• Time optimal \(d\)-list colouring of a graph
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Distributed spanner approximation
• Distributed coloring of graphs with an optimal number of colors
• Distributed recoloring
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• Distributed arboricity-dependent graph coloring via all-to-all communication
• Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Distributed (+1)-coloring via ultrafast graph shattering
• Optimal distributed coloring algorithms for planar graphs in the LOCAL model
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• Distributed Lower Bounds for Ruling Sets
• A topological perspective on distributed network algorithms
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
• Node and edge averaged complexities of local graph problems
• Distributed ∆-coloring plays hide-and-seek
• scientific article; zbMATH DE number 7758308 (Why is no real title available?)
• A note on the network coloring game: a randomized distributed (+1)-coloring algorithm
• Improved dynamic colouring of sparse graphs
• Faster deterministic distributed MIS and approximate matching
• Local conflict coloring revisited: Linial for lists
• Coloring fast without learning your neighbors' colors
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Distributed computing in the asynchronous LOCAL model
• Graph coloring via degeneracy in streaming and other space-conscious models
• Locally-iterative (+1)-coloring in sublinear (in ) rounds
• Adaptive massively parallel coloring in sparse graphs
• Parallel derandomization for coloring
• Distributed edge coloring in time polylogarithmic in \({\Delta }\)
• Min-Max correlation clustering via neighborhood similarity
• A fast coloring oracle for average case hypergraphs

This page was built for publication: An optimal distributed \((\Delta+1)\)-coloring algorithm?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230309)