Lower Bounds for the Distributed Computation of Degeneracy and k-Core

The degeneracy of a graph $G$ is the maximum integer $k$ such that $G$ has a non-empty $k$-core, where the $k$-core is the largest induced subgraph with minimum degree $k$. Computing the $k$-core of a graph $G$ is P-complete. In the decentralized setting, the sequential peeling algorithm can be distributed so that the core value of every node, i.e., the largest integer $k$ for which the node belongs to the $k$-core, is computed in $O(n)$ rounds in $n$-node networks, where adjacent nodes exchange only $O(\log n)$ bits at each round, i.e., in the standard CONGEST model. However, while $Ω(D)$ rounds is a trivial lower bound for these problems in networks of diameter $D$, this does not rule out the existence of an algorithm running in $O(D)+o(n)$ rounds in CONGEST, as it is the case for many very important graph problems, including MST. We show that it is unlikely that such an algorithm exists, or, if it does exist, then it requires $\tildeΩ(\sqrt{n})$ rounds. Specifically, our first main result states that, for any $ε>0$, approximating the degeneracy up to a multiplicative factor $2-ε$ requires $\tildeΩ(\sqrt{n})$ rounds in CONGEST even in networks of diameter $O(\log n)$, and still $\tildeΩ(n^{1/3})$ rounds in networks of constant diameter. We also show that improving this lower bound seems challenging, as we demonstrate that the newer frameworks cannot be used as black boxes to obtain a better lower bound for degeneracy. Our second main result provides a better bound, albeit conditional. It states that, unless the well-known circuit value problem (CVP) admits a parallel polynomial speedup -- an outcome considered unlikely -- it holds that, for every $ε>δ>0$, deciding whether a graph is 2-degenerate cannot be solved in $O(D+ n^{1-ε})$ rounds with $O(n^δ)$-time parallel local computation per round at each node.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.21511
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Lower Bounds for the Distributed Computation of Degeneracy and k-Core

Cristina G. Fernandes, Pedro Montealegre, Marcos A. Kiwi, Iván Rapaport et al.
arXiv (Cornell University)
Complexity and Algorithms in Graphs
preprint

Lower Bounds for the Distributed Computation of Degeneracy and k-Core

Cristina G. Fernandes, Pedro Montealegre, Marcos A. Kiwi, Iván Rapaport, Lélia Blin, Pierre Fraigniaud, Yan S. Couto
preprint en

Abstract

The degeneracy of a graph $G$ is the maximum integer $k$ such that $G$ has a non-empty $k$-core, where the $k$-core is the largest induced subgraph with minimum degree $k$. Computing the $k$-core of a graph $G$ is P-complete. In the decentralized setting, the sequential peeling algorithm can be distributed so that the core value of every node, i.e., the largest integer $k$ for which the node belongs to the $k$-core, is computed in $O(n)$ rounds in $n$-node networks, where adjacent nodes exchange only $O(\log n)$ bits at each round, i.e., in the standard CONGEST model. However, while $Ω(D)$ rounds is a trivial lower bound for these problems in networks of diameter $D$, this does not rule out the existence of an algorithm running in $O(D)+o(n)$ rounds in CONGEST, as it is the case for many very important graph problems, including MST. We show that it is unlikely that such an algorithm exists, or, if it does exist, then it requires $\tildeΩ(\sqrt{n})$ rounds. Specifically, our first main result states that, for any $ε>0$, approximating the degeneracy up to a multiplicative factor $2-ε$ requires $\tildeΩ(\sqrt{n})$ rounds in CONGEST even in networks of diameter $O(\log n)$, and still $\tildeΩ(n^{1/3})$ rounds in networks of constant diameter. We also show that improving this lower bound seems challenging, as we demonstrate that the newer frameworks cannot be used as black boxes to obtain a better lower bound for degeneracy. Our second main result provides a better bound, albeit conditional. It states that, unless the well-known circuit value problem (CVP) admits a parallel polynomial speedup -- an outcome considered unlikely -- it holds that, for every $ε>δ>0$, deciding whether a graph is 2-degenerate cannot be solved in $O(D+ n^{1-ε})$ rounds with $O(n^δ)$-time parallel local computation per round at each node.

arXiv (Cornell University)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon