Metraipolis › archive › dc_e9959fa0ca64

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

Source

arXiv (en)

Original

https://arxiv.org/abs/2608.10135

License (as archived)

CC0-1.0

Archived

2026-10-19T06:36:59.900Z

SHA-256 of the archived text

13f58eef94dc6c62a16fee6494ff18935ddaa69be1a970b9dde854534f89eb0a

Stable URL of this page

https://metraipolis.com/documento/dc_e9959fa0ca64

How to cite

Fixed-Threshold Peeling in Sublinear MPC: Round-Approximation Tradeoffs and Applications — arXiv:2608.10135 — arXiv (en), https://arxiv.org/abs/2608.10135 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e9959fa0ca64 (Metraipolis archive dc_e9959fa0ca64, sha256 13f58eef94dc6c62a16fee6494ff18935ddaa69be1a970b9dde854534f89eb0a)

@misc{dce9959fa0ca64,
  title = {Fixed-Threshold Peeling in Sublinear MPC: Round-Approximation Tradeoffs and Applications — arXiv:2608.10135},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.10135},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e9959fa0ca64; sha256 13f58eef94dc6c62a16fee6494ff18935ddaa69be1a970b9dde854534f89eb0a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.10135. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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ć [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ć [ICML 2019], again giving a round-approximation tradeoff.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-12 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.10135 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T06:28:19.211Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-12?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).