The Complexity of (Δ + 1)-Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Researchers

  • Yi-Jun Chang
  • Manuela Fischer
  • Mohsen Ghaffari
  • Jara Uitto
  • Yufan Zheng

Research units

  • Eidgenössische Technische Hochschule Zürich - ETH Zürich
  • University of Michigan
  • University of Freiburg

Abstract

In this paper, we present new randomized algorithms that improve the complexity of the classic (Δ+1)-coloring problem, and its generalization (Δ+1)-list-coloring, in three well-studied models of distributed, parallel, and centralized computation: Distributed Congested Clique: We present an O(1)-round randomized algorithm for (Δ + 1)-list-coloring in the congested clique model of distributed computing. This settles the asymptotic complexity of this problem. It moreover improves upon the O(log* Δ)-round randomized algorithms of Parter and Su [DISC'18] and O((log log Δ)⋅ log* Δ)-round randomized algorithm of Parter [ICALP'18]. Massively Parallel Computation: We present a randomized (Δ + 1)-list-coloring algorithm with round complexity O(√ log log n ) in the Massively Parallel Computation (MPC) model with strongly sublinear memory per machine. This algorithm uses a memory of O(nα) per machine, for any desirable constant α > 0, and a total memory of Õ (m), where m is the number of edges in the graph. Notably, this is the first coloring algorithm with sublogarithmic round complexity, in the sublinear memory regime of MPC. For the quasilinear memory regime of MPC, an O(1)-round algorithm was given very recently by Assadi et al. [SODA'19]. Centralized Local Computation: We show that (Δ + 1)-list-coloring can be solved by a randomized algorithm with query complexity Δ O(1) … O(log n), in the centralized local computation model. The previous state of the art for (Δ+1)-list-coloring in the centralized local computation model are based on simulation of known LOCAL algorithms. The deterministic O(√ Δ poly log Δ + log* n)-round LOCAL algorithm of Fraigniaud et al. [FOCS'16] can be implemented in the centralized local computation model with query complexity ΔO(√ Δ poly log Δ) … O(log* n); the randomized O(log* Δ) + 2^O(√ log log n)-round LOCAL algorithm of Chang et al. [STOC'18] can be implemented in the centralized local computation model with query complexity ΔO(log* Δ) … O(log n).

Details

Original languageEnglish
Title of host publicationPODC '19 -Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
Publication statusPublished - 2019
MoE publication typeA4 Article in a conference publication
EventACM Symposium on Principles of Distributed Computing - Toronto, Canada
Duration: 29 Jul 20192 Aug 2019
Conference number: 38

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
CountryCanada
CityToronto
Period29/07/201902/08/2019

ID: 38157667