Fixed-Threshold Peeling in Sublinear MPC: Round-Approximation Tradeoffs and Applications

Abstract

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 and achieve the following round-approximation tradeoffs. For density-dependent edge orientation, given any integer $t>0$, we compute an orientation with maximum out-degree at most $(2+\epsilon )(t+1)\alpha (G)$ in $O({\lg }^{1/(t+2)}n\cdot \mathrm{poly}(\lg \lg n))$ rounds, where $\alpha (G)$ denotes the minimum possible maximum out-degree of an orientation of $G$. In the $\mathrm{poly}(\lg \lg n)$-round regime, 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]. We obtain a similar improvement for density-dependent coloring. For densest subgraph, we obtain a $(4+\epsilon )$-approximation in $\tilde{O}({\lg }^{1/3}n)$ MPC rounds and a $(6+\epsilon )$-approximation in $\tilde{O}({\lg }^{1/4}n)$ MPC rounds. This improves the $\tilde{O}(\sqrt{\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 $\Theta (\sqrt{\lg n})$ round-complexity barrier in the sub-linear MPC model. For $k$-core decomposition, given any integer $t>0$, we compute approximate coreness values within a factor of $(2+\epsilon )(t+1)$ in $O({\lg }^{1/(t+2)}n\cdot \mathrm{poly}(\lg \lg n))$ MPC rounds for any integer $t>0$. This improves the $\tilde{O}(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrović [ICML 2019], again giving a round-approximation tradeoff.