Distributed algorithms face high round complexity for graph degeneracy estimation
Lower Bounds for the Distributed Computation of Degeneracy and k-Core
Distributed, Parallel, and Cluster Computing
Summary
Degeneracy measures how densely connected parts of a network are, found by peeling away less connected nodes. The authors study how quickly computers in a distributed network can find this measure when only limited information is shared each step. They show it takes a surprisingly long time—much longer than for many other network tasks—even on networks with small diameter. This means fast distributed algorithms for approximating or deciding degeneracy likely need many communication rounds or rely on unlikely breakthroughs in computing theory.
What this means in practice
- •For network protocol designers: Avoid assuming quick distributed degeneracy computations in network protocols due to inherent communication lower bounds.
- •For distributed system architects: Plan system designs that do not rely on fast approximations of graph degeneracy or k-core in networks with limited messaging bandwidth.
A theory result. No direct application yet.
Authors
Lélia Blin, Yan S. Couto, Cristina G. Fernandes, Pierre Fraigniaud, Marcos Kiwi, Pedro Montealegre, Ivan Rapaport
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.