Search Results

A number of fundamental graph problems admit simple algorithms based on iterative peeling: repeatedly remove all vertices whose current degree is below a fixed threshold. This paradigm underlies algorithms for density-dependent edge orientation, density-dependent coloring, densest subgraph, and k-core decomposition. In this paper, we study these problems in the sub-linear MPC model. We achieve the following round-approximation tradeoffs for this family of problems. For any constant δ ∈ (0,1), our algorithms use O(n^δ) local memory and Õ(m+n^{1+δ}) global memory. - Density-dependent edge orientation. For any integer t > 0, we compute an orientation with maximum out-degree at most (2+ε)(t+1)α(G) in O(lg^{1/(t+2)} n ⋅ poly(lg lg n)) rounds, where α(G) denotes the minimum possible maximum out-degree of an orientation of G. In the poly(lg lg n)-round regime, obtained by setting t = ⌈lg lg n/lg lg lg n⌉, this gives an O(lg lg n/lg lg lg n)-approximation, improving the approximation factor of the recent work by Ghaffari and Grunau [PODC 2025]. - Densest subgraph. We obtain a (4+ε)-approximation in Õ(lg^{1/3} n) MPC rounds and a (6+ε)-approximation in Õ(lg^{1/4} n) MPC rounds. This improves the Õ(√{lg n}) round complexity of Ghaffari, Lattanzi, and Mitrović [ICML 2019] with a slightly larger approximation factor. This is the first O(1)-approximate algorithm for densest subgraph to break the Θ(√{lg n}) round-complexity barrier in the sub-linear MPC model. - k-core decomposition. For any integer t > 0, we compute approximate coreness values within a factor of (2+ε)(t+1) in O(lg^{1/(t+2)} n ⋅ poly(lg lg n)) MPC rounds. This improves the Õ(√{lg n}) round complexity of Ghaffari, Lattanzi, and Mitrović [ICML 2019], again giving a round-approximation tradeoff. - Density-dependent coloring. By combining our orientation algorithm with standard coloring reductions, we obtain a coloring with (2+ε)(t+1)α(G)+1 colors in O(lg^{1/(t+2)} n ⋅ poly(lg lg n)) MPC rounds. In particular, this improves the approximation obtainable in poly(lg lg n) rounds over Ghaffari and Grunau [PODC 2025].