Adaptive Massively Parallel Coloring in Sparse Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913338627194880 |
|---|---|
| author | Latypov, Rustam Maus, Yannic Pai, Shreyas Uitto, Jara |
| author_facet | Latypov, Rustam Maus, Yannic Pai, Shreyas Uitto, Jara |
| contents | 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$.
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 $\text{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13755 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Adaptive Massively Parallel Coloring in Sparse Graphs Latypov, Rustam Maus, Yannic Pai, Shreyas Uitto, Jara Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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$. 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 $\text{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. |
| title | Adaptive Massively Parallel Coloring in Sparse Graphs |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.13755 |