License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.39
URN: urn:nbn:de:0030-drops-98286
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9828/
Go to the corresponding LIPIcs Volume Portal

Parter, Merav ; Su, Hsin-Hao

Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds

pdf-format:
LIPIcs-DISC-2018-39.pdf (0.9 MB)

Abstract

(Delta+1)-vertex coloring is one of the most fundamental symmetry breaking graph problems, receiving tremendous amount of attention over the last decades. We consider the congested clique model where in each round, every pair of vertices can exchange O(log n) bits of information.
In a recent breakthrough, Yi-Jun Chang, Wenzheng Li, and Seth Pettie [CLP-STOC'18] presented a randomized (Delta+1)-list coloring algorithm in the LOCAL model that works in O(log^*n+Det_{deg}(log log n)) rounds, where Det_{deg}(n') is the deterministic LOCAL complexity of (deg+1)-list coloring algorithm on n'-vertex graphs. Unfortunately, the CLP algorithm uses large messages and hence cannot be efficiently implemented in the congested clique model when the maximum degree Delta is large (in particular, when Delta=omega(sqrt{n})).
Merav Parter [P-ICALP'18] recently provided a randomized (Delta+1)-coloring algorithm in O(log log Delta * log^* Delta) congested clique rounds based on a careful partitioning of the input graph into almost-independent subgraphs with maximum degree sqrt{n}. In this work, we significantly improve upon this result and present a randomized (Delta+1)-coloring algorithm with O(log^* Delta) rounds, with high probability. At the heart of our algorithm is an adaptation of the CLP algorithm for coloring a subgraph with o(n) vertices and maximum degree Omega(n^{5/8}) in O(log^* Delta) rounds. The approach is built upon a combination of techniques, this includes: the graph sparsification of [Parter-ICALP'18], and a palette sampling technique adopted to the CLP framework.

BibTeX - Entry

@InProceedings{parter_et_al:LIPIcs:2018:9828,
  author =	{Merav Parter and Hsin-Hao Su},
  title =	{{Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9828},
  URN =		{urn:nbn:de:0030-drops-98286},
  doi =		{10.4230/LIPIcs.DISC.2018.39},
  annote =	{Keywords: Distributed Graph Algorithms, Coloring, congested clique}
}

Keywords: Distributed Graph Algorithms, Coloring, congested clique
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI