Adaptive Massively Parallel Coloring in Sparse Graphs

• Published in: arXiv.org 2024-02
• Main Authors: Latypov, Rustam, Maus, Yannic, Pai, Shreyas, Uitto, Jara
• Format: Article
• Language: English
• Subjects: Algorithms; Broken symmetry; Computation; Graph coloring; Graphs; Nodes; Parallel processing
• ISSN: 2331-8422

Classic symmetry-breaking problems on graphs have gained a lot of attention in models of modern parallel computation. The Adaptive Massively Parallel Computation (AMPC) is a model that captures central challenges in data center computations. Chang et al. [PODC'2019] gave an extremely fast, constant time, algorithm for the \((\Delta + 1)\)-coloring problem, where \(\Delta\) is the maximum degree of an input graph of \(n\) nodes. The algorithm works in the most restrictive low-space setting, where each machine has \(n^{\delta}\) local space for a constant \(0 < \delta < 1\). In this work, we study the vertex-coloring problem in sparse graphs parameterized by their arboricity \(\alpha\), a standard measure for sparsity. We give deterministic algorithms that in constant, or almost constant, time give \(\text{poly}(\alpha)\) and \(O(\alpha)\)-colorings, where \(\alpha\) can be arbitrarily smaller than \(\Delta\). A strong and standard approach to compute arboricity-dependent colorings is through the Nash-Williams forest decomposition, which gives rise to an (acyclic) orientation of the edges such that each node has a small outdegree. Our main technical contribution is giving efficient deterministic algorithms to compute these orientations and showing how to leverage them to find colorings in low-space AMPC. A key technical challenge is that the color of a node may depend on almost all of the other nodes in the graph and these dependencies cannot be stored on a single machine. Nevertheless, our novel and careful exploration technique yields the orientation, and the arboricity-dependent coloring, with a sublinear number of adaptive queries per node.