Adaptive Massively Parallel Coloring in Sparse Graphs
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
11
Series
PODC 2024 - Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing, pp. 508-518
Abstract
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 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 low-space 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 vertex-coloring 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 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 out-degree.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.Description
Publisher Copyright: © 2024 Association for Computing Machinery. All rights reserved.
Other note
Citation
Latypov, R, Maus, Y, Pai, S & Uitto, J 2024, Adaptive Massively Parallel Coloring in Sparse Graphs. in PODC 2024 - Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing. ACM, pp. 508-518, ACM Symposium on Principles of Distributed Computing, Nantes, France, 17/06/2024. https://doi.org/10.1145/3662158.3662821