Density-Dependent Graph Orientation and Coloring in Scalable MPC

Mohsen Ghaffari, Christoph Grunau · 2026

Read Density-Dependent Graph Orientation and Coloring in Scalable MPC by Mohsen Ghaffari, Christoph Grunau (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10639.txt.

Introduction

Mohsen Ghaffari and Christoph Grunau give massively parallel algorithms for orienting and coloring graphs by subgraph density, in the strongly sublinear memory regime. Their methods run in very few rounds, a poly-log-log count that breaks a long-standing square-root barrier. The orientation keeps maximum outdegree low, scaled by the density of the densest subgraph, and the coloring uses a matching number of colors. The result improves on the best prior density-dependent orientation algorithm and a pattern common to many scalable MPC methods.

Catalog record

CREATORMohsen Ghaffari, Christoph Grunau
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81510
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.10639

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Density-Dependent Graph Orientation and Coloring in Scalable MPC Mohsen Ghaffari, Christoph Grunau Abstract 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 ) \operatorname{\text{{\rm poly}}}(\log\log n) rounds and compute an orientation of the edges with maximum outdegree O ⁡ ( α ​ log ⁡ log ​ n ) O(\alpha\log\log n) as well as a coloring of the vertices with O ⁡ ( α ​ log ⁡ log ​ n ) O(\alpha\log\log n) colors. Here, α \alpha denotes the density of the densest subgraph. Our algorithm’s round complexity is notable because it breaks the Θ ~ ​ ( log ⁡ n ) \widetilde{\Theta}(\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. 1 Introduction We present the first \operatorname{\text{{\rm poly}}}(\log\log n) -round Scalable Massively Parallel Computation (MPC) algorithms for low out-degree orientation and coloring as a function of subgraph density (or equivalently, arboricity). We first review the context and state of the art, and then state our results. 1.1 Models and Basic Definitions Massively Parallel Computation Model. We work with the massively parallel computation (MPC) model [ 32 , 27 , 7 , 1 ] , which has become de facto the standard theoretical abstraction for large-scale distributed data processing frameworks such as MapReduce [ 16 ] , Hadoop [ 45 ] , Spark [ 46 ] and Dryad [ 31 ] . We provide a brief definition next; please see the recent book of Im et. al. [ 30 ] or the lecture notes of Ghaffari [ 38 ] for more. The distributed system is composed of M machines, and the data is distributed among them (arbitrarily). In the case of graph problems, this data is the input graph G=(V,E) , for which we also usually use the notations m=|E| and n=|V| . Each machine is assumed to have a local memory capacity of S words. A word is simply O(\log n) bits and can describe, for instance, a single vertex or edge. We usually refer to the total summation of memories, which is simply MS , as the global memory of the system. Trivially, we need that MS=\Omega(m+n) . Computation proceeds in synchronous rounds. Per round, each machine can perform some computation on the data it holds and then send some information to other machines. The only communication constraint is that the total amount of data that one machine sends or receives, in a round, cannot exceed its memory capacity S . The primary measure of interest is the round complexity of the algorithm. The setting where S can be polynomially smaller than n — concretely S\leq n^{\delta} for a constant \delta\in(0,1) — has been called the strongly sublinear memory regime , and this indicates the most challenging (and also the most desirable) domain for algorithm design. Algorithms in this regime are frequently referred to as Scalable MPC algorithms , and this is the focus of the present paper. LOCAL Model. Many state-of-the-art (scalable) MPC algorithms for graph problems are designed based on approaches in the more classic LOCAL model of distributed computing [ 37 , 41 ] . So we briefly recall this model: the graph G=(V,E) represents an abstraction of the computer network, with one computer per node, and it has an O(\log n) -bit identifier. Per round, each computer/node can send one message to each of its neighbors in G . At the start, each node knows only its neighbors. At the end of the computation, each node should know its own part of the output, e.g., its color in a coloring. Again the primary measure is the round complexity. Densest Subgraph Density, and Abroricity. The maximum subgraph density (often, simply subgraph density ) of a graph G is defined as \alpha(G)=\max_{S\subseteq V}\{\frac{|E(S)|}{|S|}\} , where E(S) denotes the set of edges with both endpoints in S . A closely related measure is the graph’s arboricity \lambda(G) , defined as \lambda(G)=\max_{S\subseteq V}\{\lceil\frac{|E(S)|}{|S|-1}\rceil\} , which is also equivalent to the the minimum number of forests into which the edges E can be partitioned [ 39 , 40 , 44 ] . Note that \alpha(G)\leq\lambda(G)\leq\alpha(G)+1 . Low Out-degree Orientation. We are interested in edge orientations with small maximum outdegree. In any orientation, the maximum outdegree is lower bounded by the subgraph density \alpha(G) . We want our outdegree bound to be close to this. Since \alpha(G) and \lambda(G) are equal up to a +1 , our results can be stated in terms of either of these, and we use arboricity \lambda=\lambda(G) from now on (also since the special case of \lambda=1 nicely coincides with forests). 1.2 State of the Art in Scalable MPC and Distributed Algorithms LOCAL Algorithms. A simple LOCAL-model algorithm of Barenboim and Elkin [ 6 ] gives an orientation of edges with outdegree at most (2+\varepsilon)\lambda , for any constant \varepsilon>0 , in O(\log n) rounds: per round, simultaneously remove all nodes of degree at most (2+\varepsilon)\lambda in the remaining graph and mark their edges as outgoing (if both endpoints of an edge are removed, orient the edge arbitrarily, e.g., toward the higher identifier). This O(\log n) round complexity is optimal: even when \lambda=1 , computing any orientation with O(1) outdegree requires \Omega(\log n) rounds, as implied by a lower bound of Linial [ 37 ] . There are also algorithms [ 25 , 43 ] that computes ((1+\varepsilon)\lambda) -outdegree orientation in \operatorname{\text{{\rm poly}}}(\log n) rounds. One can easily run these LOCAL algorithms, and especially the simple O(\log n) round one, in scalable MPC. However, given the power of the MPC model and the costly nature of each round in the large-scale computation world modeled by MPC, it is imperative to obtain algorithms with a significantly lower round complexity. Scalable MPC Algorithms. Ghaffari, Lattanzi, and Mitrovic [ 23 , Section 4] presented a scalable MPC algorithm that computes an oritentation with outdegree at most (2+\varepsilon)\lambda in \widetilde{O}(\sqrt{\log n}) 1 1 1 Here and throughout, we write f(n)=\widetilde{O}(g(n)) to suppress factors polylogarithmic in n ; that is, f(n)=\widetilde{O}(g(n)) if there exists a constant k\geq 0 such that f(n)=O\bigl(g(n)\,(\log n)^{k}\bigr) . rounds. 2 2 2 We comment that they state this more generally for coreness decomposition , but that’s done by simply running the algorithm for every k=(1+\varepsilon)^{i} coreness/arboricity estimate in parallel. See [ 38 , Exercise 2.3] for a short sketch. This is based on a fast simulation of the above LOCAL algorithm, using sparsification ideas in the style of the work of Ghaffari and Uitto [ 26 ] . We will later give more explanations about this approach and its \widetilde{\Theta}(\sqrt{\log n}) bottleneck. To the best of our knowledge, this \widetilde{O}(\sqrt{\log n}) bound is state-of-the-art round complexity for scalable MPC orientation, in fact even if we allow much higher maximum outdegree bounds, e.g. \lambda\cdot\operatorname{\text{{\rm poly}}}(\log n) . There is one notable exception to the above: in the special case of \lambda=1 —i.e., when G is simply a forest—a recent scalable MPC algorithm of Grunau et al. [

Read the complete text