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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Tutkijat

Organisaatiot

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

Kuvaus

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).

Yksityiskohdat

AlkuperäiskieliEnglanti
OtsikkoPODC '19 -Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
TilaJulkaistu - 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM Symposium on Principles of Distributed Computing - Toronto, Kanada
Kesto: 29 heinäkuuta 20192 elokuuta 2019
Konferenssinumero: 38

Conference

ConferenceACM Symposium on Principles of Distributed Computing
LyhennettäPODC
MaaKanada
KaupunkiToronto
Ajanjakso29/07/201902/08/2019

ID: 38157667