Skip to Main content Skip to Navigation
Conference papers

Local Conflict Coloring

Pierre Fraigniaud 1 Marc Heinrich 1 Adrian Kosowski 1
1 GANG - Networks, Graphs and Algorithms
IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : Locally finding a solution to symmetry-breaking tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in distributed network computing. More recently, it has also become a challenge in the framework of centralized local computation. We introduce conflict coloring as a general symmetry-breaking task that includes all the aforementioned tasks as specific instantiations --- conflict coloring includes all locally checkable labeling tasks from [Naor&Stockmeyer, STOC 1993]. Conflict coloring is characterized by two parameters $l$ and $d$, where the former measures the amount of freedom given to the nodes for selecting their colors, and the latter measures the number of constraints which colors of adjacent nodes are subject to. We show that, in the standard LOCAL model for distributed network computing, if $l/d > \Delta$, then conflict coloring can be solved in $\tilde O(\sqrt{\Delta})+\log^*n$ rounds in $n$-node graphs with maximum degree $\Delta$, where $\tilde O$ ignores the polylog factors in $\Delta$. The dependency in~$n$ is optimal, as a consequence of the $\Omega(\log^*n)$ lower bound by [Linial, SIAM J. Comp. 1992] for $(\Delta+1)$-coloring. An important special case of our result is a significant improvement over the best known algorithm for distributed $(\Delta+1)$-coloring due to [Barenboim, PODC 2015], which required $\tilde O(\Delta^{3/4})+\log^*n$ rounds. Improvements for other variants of coloring, including $(\Delta+1)$-list-coloring, $(2\Delta-1)$-edge-coloring, $T$-coloring, etc., also follow from our general result on conflict coloring. Likewise, in the framework of centralized local computation algorithms (LCAs), our general result yields an LCA which requires a smaller number of probes than the previously best known algorithm for vertex-coloring, and works for a wide range of coloring problems.
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download
Contributor : Adrian Kosowski Connect in order to contact the contributor
Submitted on : Thursday, February 2, 2017 - 11:57:00 AM
Last modification on : Friday, January 21, 2022 - 3:19:30 AM
Long-term archiving on: : Friday, May 5, 2017 - 1:12:49 PM


Files produced by the author(s)


  • HAL Id : hal-01223494, version 2
  • ARXIV : 1511.01287


Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski. Local Conflict Coloring. FOCS 2016 - 57th Annual IEEE Symposium on Foundations of Computer Science, Oct 2016, New Brunswick, NJ, United States. ⟨hal-01223494v2⟩



Les métriques sont temporairement indisponibles