Deterministic 3-Coloring of Trees in the Sublinear MPC model
share
We present deterministic O(log^2 log n) time sublinear Massively Parallel Computation (MPC) algorithms for 3-coloring, maximal independent set and maximal matching in trees with n nodes. In accordance with the sublinear MPC regime, our algorithms run on machines that have memory as little as O(n^δ) for any arbitrary constant 0<δ<1. Furthermore, our algorithms use only O(n) global memory. Our main result is the 3-coloring algorithm, which contrasts the probabilistic 4-coloring algorithm of Ghaffari, Grunau and Jin [DISC'20]. The maximal independent set and maximal matching algorithms follow in O(1) time after obtaining the coloring. The key ingredient of our 3-coloring algorithm is an O(log^2 log n) time MPC implementation of a variant of the rake-and-compress tree decomposition used by Chang and Pettie [FOCS'17], which is closely related to the H-partition by Barenboim and Elkin [PODC'08]. When restricting to trees of constant maximum degree, we bring the runtime down to O(loglog n).
READ FULL TEXT