Simple, deterministic, constant-round coloring in congested clique and MPC
Czumaj, Artur
Davies, Peter
Parter, Merav
General Mathematics
General Computer Science
We settle the complexity of the (∆ + 1)-coloring and (∆ + 1)-list coloring problems intheCONGESTED CLIQUEmodel by presenting a simpledeterministicalgorithm for both problemsrunning in a constant number of rounds. This matches the complexity of the recent breakthroughrandomizedconstant-round (∆ + 1)-list coloring algorithm due to Chang et al. [Proceedings of the38th ACM Symposium on Principles of Distributed Computing, 2019] and significantly improvesupon the state-of-the-artO(log ∆)-round deterministic (∆ + 1)-coloring bound of Parter [Proceed-ings of the 45th Annual International Colloquium on Automata, Languages and Programming]. Aremarkable property of our algorithm is its simplicity. Whereas the state-of-the-artrandomizedal-gorithms for this problem are based on the quite involved local coloring algorithm of Chang, Li, andPettie [Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018],our algorithm can be described in just a few lines. At a high level, it applies a careful derandomiza-tion of a recursive procedure which partitions the nodes and their respective palettes into separatebins. We show that afterO(1) recursion steps, the remaining uncolored subgraph within each bin haslinear size and thus can be solved locally by collecting it to a single node. This algorithm can alsobe implemented in the massively parallel computation (MPC) model provided that each machine haslinear (inn, the number of nodes in the input graph) space. We also show an extension of our algo-rithm to theMPCregime, in which machines havesublinearspace: we present the first deterministic(∆ + 1)-list coloring algorithm designed for sublinear-spaceMPC, which runs inO(log ∆ + log logn)rounds.
Society for Industrial & Applied Mathematics
2021
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/15271
Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring in congested clique and MPC. <i>SIAM Journal on Computing</i>. 2021;50(5):1603-1626. doi:<a href="https://doi.org/10.1137/20m1366502">10.1137/20m1366502</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1137/20m1366502
info:eu-repo/semantics/altIdentifier/issn/0097-5397
info:eu-repo/semantics/altIdentifier/issn/1095-7111
info:eu-repo/grantAgreement/EC/H2020/754411
info:eu-repo/semantics/closedAccess