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 \operatorname{poly}(\lg \lg n))$ rounds, where $\alpha(G)$ denotes the minimum possible maximum out-degree of an orientation of $G$. In the $\operatorname{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 $\widetilde O(\lg^{1/3} n)$ MPC rounds and a $(6+\epsilon)$-approximation in $\widetilde O(\lg^{1/4} n)$ MPC rounds. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrovi\'c [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 \operatorname{poly}(\lg \lg n))$ MPC rounds for any integer $t>0$. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrovi\'c [ICML 2019], again giving a round-approximation tradeoff.