research-article

Public Access

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

Authors:

Yufan ZhengAuthors Info & Claims

PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

Pages 471 - 480

https://doi.org/10.1145/3293611.3331607

Published: 16 July 2019 Publication History

PDF eReader

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

References

[1]

Kook Jin Ahn and Sudipto Guha. 2015. Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching Under Resource Constraints. In Proc. SPAA. 202--211.

Abstract

References

Cited By

Index Terms

Recommendations

An optimal distributed (Δ+1)-coloring algorithm?

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Simple, Deterministic, Constant-Round Coloring in the Congested Clique

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations