Projects per year
Abstract
Classic symmetrybreaking 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 the central challenges in data center computations. Chang et al. [PODC'2019] gave an extremely fast, constant time, algorithm for the (δ+1)coloring problem, where Δis the maximum degree of an input graph of n nodes. The algorithm works in the most restrictive lowspace setting, where each machine has n^{δ} local space for a constant 0 < δ < 1.The standard approaches for (Δ+ 1)coloring are ignorant about the graph topology in the following sense: They exploit the property that any partial coloring can be extended to a feasible (Δ+ 1)coloring of the whole graph. For most graphs, the chromatic number is much smaller than Δ+ 1 and we would like to find colorings with fewer colors. However, as soon as we have fewer than Δ+ 1 colors, it might not be possible to complete partial colorings.In this work, we study the vertexcoloring problem in sparse graphs parameterized by their arboricity α, a standard measure for sparsity. We give deterministic algorithms that in constant, or almost constant, time give poly α and O(α)colorings, where α can be arbitrarily smaller than δ. A strong and standard approach to compute arboricitydependent colorings is through the NashWilliams 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 lowspace 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 arboricitydependent coloring, with a sublinear number of adaptive queries per node.
Original language  English 

Title of host publication  PODC 2024  Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing 
Publisher  ACM 
Pages  508518 
Number of pages  11 
ISBN (Electronic)  9798400706684 
DOIs  
Publication status  Published  17 Jun 2024 
MoE publication type  A4 Conference publication 
Event  ACM Symposium on Principles of Distributed Computing  Nantes, France Duration: 17 Jun 2024 → 21 Jun 2024 
Conference
Conference  ACM Symposium on Principles of Distributed Computing 

Abbreviated title  PODC 
Country/Territory  France 
City  Nantes 
Period  17/06/2024 → 21/06/2024 
Keywords
 adaptive massively parallel computation
 graph coloring
Fingerprint
Dive into the research topics of 'Adaptive Massively Parallel Coloring in Sparse Graphs'. Together they form a unique fingerprint.Projects
 1 Active

: Massively Parallel Algorithms for LargeScale Graph Problems
Uitto, J. (Principal investigator), Cambus, M. (Project Member), Latypov, R. (Project Member) & Pai, S. (Project Member)
01/09/2020 → 27/04/2025
Project: Academy of Finland: Other research funding