跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.21511 · v1

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

退化性与k-核的分布式计算下界

首次提交 2026-11-17 02:08
版本更新 2026-11-17 02:08
雷达观测 2026-11-17 16:10
arXiv ↗PDF ↗

摘要

The degeneracy of a graph GG is the maximum integer kk such that GG has a non-empty kk-core, where the kk-core is the largest induced subgraph with minimum degree kk. Computing the kk-core of a graph GG 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 kk for which the node belongs to the kk-core, is computed in O(n)O(n) rounds in nn-node networks, where adjacent nodes exchange only O(log⁡n)O(\log n) bits at each round, i.e., in the standard CONGEST model. However, while Ω(D)Ω(D) rounds is a trivial lower bound for these problems in networks of diameter DD, this does not rule out the existence of an algorithm running in O(D)+o(n)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 Ω~(n)\tildeΩ(\sqrt{n}) rounds. Specifically, our first main result states that, for any ε>0ε>0, approximating the degeneracy up to a multiplicative factor 2−ε2-ε requires Ω~(n)\tildeΩ(\sqrt{n}) rounds in CONGEST even in networks of diameter O(log⁡n)O(\log n), and still Ω~(n1/3)\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ε>δ>0, deciding whether a graph is 2-degenerate cannot be solved in O(D+n1−ε)O(D+ n^{1-ε}) rounds with O(nδ)O(n^δ)-time parallel local computation per round at each node.

AI 论文解读

基于摘要 · 非全文审阅

该论文证明在CONGEST模型中,近似计算图的退化性(或判定2-退化性)需要显著超过直径D的轮数,从而排除了O(D)+o(n)轮算法的可能性。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-17 02:08 · 最新观测版本

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

The degeneracy of a graph GG is the maximum integer kk such that GG has a non-empty kk-core, where the kk-core is the largest induced subgraph with minimum degree kk. Computing the kk-core of a graph GG 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 kk for which the node belongs to the kk-core, is computed in O(n)O(n) rounds in nn-node networks, where adjacent nodes exchange only O(log⁡n)O(\log n) bits at each round, i.e., in the standard CONGEST model. However, while Ω(D)Ω(D) rounds is a trivial lower bound for these problems in networks of diameter DD, this does not rule out the existence of an algorithm running in O(D)+o(n)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 Ω~(n)\tildeΩ(\sqrt{n}) rounds. Specifically, our first main result states that, for any ε>0ε>0, approximating the degeneracy up to a multiplicative factor 2−ε2-ε requires Ω~(n)\tildeΩ(\sqrt{n}) rounds in CONGEST even in networks of diameter O(log⁡n)O(\log n), and still Ω~(n1/3)\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ε>δ>0, deciding whether a graph is 2-degenerate cannot be solved in O(D+n1−ε)O(D+ n^{1-ε}) rounds with O(nδ)O(n^δ)-time parallel local computation per round at each node.

查看此版本解读 →查看此版本原文 ↗