Density-Dependent Graph Orientation and Coloring in Scalable MPC
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910049186611200 |
|---|---|
| author | Ghaffari, Mohsen Grunau, Christoph |
| author_facet | Ghaffari, Mohsen Grunau, Christoph |
| contents | This paper presents massively parallel computation (MPC) algorithms in the strongly sublinear memory regime (aka, scalable MPC) for orienting and coloring graphs as a function of its subgraph density. Our algorithms run in $poly(\log\log n)$ rounds and compute an orientation of the edges with maximum outdegree $O(α\log\log n)$ as well as a coloring of the vertices with $O(α\log\log n)$ colors. Here, $α$ denotes the density of the densest subgraph. Our algorithm's round complexity is notable because it breaks the $\tildeΘ(\sqrt{\log n})$ barrier, which applied to the previously best known density-dependent orientation algorithm [Ghaffari, Lattanzi, and Mitrovic ICML'19] and is common to many other scalable MPC algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_10639 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Density-Dependent Graph Orientation and Coloring in Scalable MPC Ghaffari, Mohsen Grunau, Christoph Data Structures and Algorithms This paper presents massively parallel computation (MPC) algorithms in the strongly sublinear memory regime (aka, scalable MPC) for orienting and coloring graphs as a function of its subgraph density. Our algorithms run in $poly(\log\log n)$ rounds and compute an orientation of the edges with maximum outdegree $O(α\log\log n)$ as well as a coloring of the vertices with $O(α\log\log n)$ colors. Here, $α$ denotes the density of the densest subgraph. Our algorithm's round complexity is notable because it breaks the $\tildeΘ(\sqrt{\log n})$ barrier, which applied to the previously best known density-dependent orientation algorithm [Ghaffari, Lattanzi, and Mitrovic ICML'19] and is common to many other scalable MPC algorithms. |
| title | Density-Dependent Graph Orientation and Coloring in Scalable MPC |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.10639 |