Coloring Trees in Massively Parallel Computation

2021/05/28 by Rustam Latypov, Latypov, Rustam, Jara Uitto +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Graph Theory and Algorithms #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.2105.13980

openalex publication_date 2021/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present O(log² log n) time 3-coloring, maximal independent set and maximal matching algorithms for trees in the Massively Parallel Computation (MPC) model. Our algorithms are deterministic, apply to arbitrary-degree trees and work in the low-space MPC model, where local memory is O(n^δ) for δ∈ (0,1) and global memory is O(m). Our main result is the 3-coloring algorithm, which contrasts the randomized, state-of-the-art 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² log n) time adaptation of the rake-and-compress tree decomposition used by Chang and Pettie [FOCS'17], and established by Miller and Reif. When restricting our attention to trees of constant degree, we bring the runtime down to O(log log n).

Related

• Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
• Conditionally Optimal Parallel Coloring of Forests
• The Complexity of (Δ+ 1)Coloring inCongested Clique, Massively Parallel Computation,and Centralized Local Computation
• Improved Deterministic (Δ+1)-Coloring in Low-Space MPC
• Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory