betaFeedback

WorksComputer Science

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

Abstract

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.

Introduction

General Objective

Finding the degeneracy of a graph is a subproblem of the kk-core decomposition problem. Recall that a graph GG is called dd-degenerate if every subgraph of GG has a vertex of degree at most dd. The minimum dd for which GG is dd-degenerate is called the degeneracy of GG, denoted by d(G)d(G). Degeneracy is a classical measure of graph sparsity, and it is within a constant factor from other important sparsity measures, including arboricity, expansion, etc. In particular, for every graph GG, if dd denotes its degeneracy, and aa its arboricity, then a≤d≤2a−1a \le d \le2a - 1. Both arboricity and degeneracy play a central role in the design of distributed graph algorithms, especially for subgraph detection [32, 45], coloring [9, 24, 33], dominating set [19] and matching [17].

Also recall that the kk-core of GG is the largest induced subgraph of GG that has minimum degree at least kk. Note that the kk-core is well-defined and unique as, for any two sets of nodes U⊆VU \subseteq V and U′⊆VU' \subseteq V, if the induced subgraphs G[U]G[U] and G[U′]G[U'] satisfy the degree condition, then so does G[U∪U′]G[U \cup U']. If GG has a nonempty kk-core, then GG is not (k−1)(k - 1)-degenerate, that is, d(G)≥kd(G) \ge k. More precisely, the degeneracy of GG is the maximum kk for which it has a nonempty kk-core. Given a node vv of a graph GG, the core value of vv is the largest kk such that vv belongs to the kk-core of GG. The concept of kk-core was introduced by Seidman [50] as a measure of social cohesion. The core value of a node can be interpreted as its level of centrality in the network, reflecting how much it is integrated within the network, as well as a measure of robustness against cascading failures [11, 13]. The applications of core values are diverse and well studied, spanning a wide range of domains, including community detection [25, 40], virus propagation [31], data pruning [8], graph visualization [3], as well as various areas of the natural sciences such as biology [21], ecology [44], neuroscience [52], and physics [43], among others. For a survey, see [38].

In this paper, we study the distributed complexity of these two important problems, i.e., of determining (or approximating) the degeneracy of a network GG, and of computing the core values of its nodes. More specifically, we consider the following problems.

Definition 1.

  • The Degeneracy problem asks all nodes to output the degeneracy d(G)d(G) of the network.

  • For α>1\alpha> 1, the α\alpha-ApproxDegeneracy problem asks each node to output an α\alpha-approximation of the degeneracy, that is, every node vv must output a value cvc_v such that d(G)≤cv≤α⋅d(G)d(G) \le c_v \le\alpha\cdot d(G).

  • For k≥0k \ge0, the kk-Degenerate problem asks all nodes to output “accept” if the network is kk-degenerate, and at least one node must output “reject” otherwise.

  • For k≥0k \ge0, the kk-Core problem asks each node to output “yes” if it is in the kk-core of the network, and “no” otherwise.

  • The CoreValue problem asks each node to output the largest integer kk for which it belongs to the kk-core of the network.

We tackle these problems in the standard CONGEST model of distributed computing in networks [48]. Recall that the CONGEST model is a synchronous, message-passing model used to analyze distributed graph algorithms. It views any (connected) graph as a network in which every node is a computing entity (e.g., a Turing machine), and where the nodes exchange messages along the edges of the graph, viewed as communication links. In an nn-node network, nodes are given distinct identifiers (IDs) in a polynomial range, i.e., each ID consumes O(log⁡n)O(\log n) bits to be stored. Computation is performed as a sequence of synchronous rounds. Specifically, all nodes of an nn-node network start at the same time and, at each round, every node (1) sends an O(log⁡n)O(\log n)-bit message to each of its neighbors, (2) receives the messages sent to it by its neighbors, and (3) performs some local computation.

The Quest for Sublinear Algorithms

In CONGEST, the network is subject to two major limitations, namely locality and bandwidth. Indeed, a piece of information emitted by a node vv at round tt may only be known, at round t+rt+r, to the nodes in the radius-rr ball around vv in the network, and a node can send and receive O(log⁡n)O(\log n) bits per round through each of its incident edges. As a consequence, even “local problems” such as detecting the presence of a 4-cycle can require Ω~(n)\widetilde{\Omega}(\sqrt{n}) rounds8 [20], and “global problems” such as computing a minimum-weight spanning tree (MST) require Ω(D)\Omega(D) rounds on networks of diameter DD [48]. Nevertheless, many networks coming from practical situations have sublinear diameter, so CONGEST algorithms running in o(n)o(n) rounds on nn-node networks with sublinear diameter are particularly interesting. Indeed, many problems admit such algorithms, including the aforementioned MST problem, which can be solved in CONGEST in O(D+nlog⁡⋆n)O(D+\sqrt{n}\log^{\star}n) rounds [23, 35]. Our main goal is to figure out whether computing degeneracy or kk-core decomposition also admits CONGEST algorithms running in o(n)o(n) rounds on networks with sublinear diameter, or whether they are “hard” in the sense that they require Ω(n)\Omega(n) rounds, regardless of the diameter.

Solving kk-DEGENERATE in CONGEST suffers from the same limitation as when computing an MST, even for k=1k=1. Indeed, solving 1-DEGENERATE requires Ω(D)\Omega(D) rounds on networks of diameter DD, merely because any distributed algorithm for 1-DEGENERATE has to distinguish between a path and a cycle. (A path has degeneracy 1 while a cycle has degeneracy 2.) On the other hand, the sequential peeling algorithm [10], which peels off a smallest degree node at every step, computes the core value of each node in sequential time O(n+m)O(n+m) on nn-node graphs with mm edges, in particular finding the degeneracy of the graph. As we will see, the peeling algorithm can easily be implemented in CONGEST, to run in O(n)O(n) rounds on nn-node networks. The main goal of this paper is to close the gap between these two bounds Ω(D)\Omega(D) and O(n)O(n). The central question addressed in this paper is therefore the following:

Do there exist CONGEST algorithms solving any of the problems in Definition 1 in O(D)+o(n)O(D)+o(n) rounds on nn-node networks with diameter DD?

The problems in Definition 1 can be partially ordered as a function of their complexities in CONGEST. For instance, an algorithm solving DEGENERACY also solves kk-DEGENERATE (if d(G)=dd(G)=d then all nodes accept whenever k≥dk\ge d, and all nodes reject otherwise). Similarly, an algorithm solving (k+1)(k+1)-CORE also solves kk-DEGENERATE (every node outputting no accepts, and every node outputting yes rejects). Moreover, an algorithm solving COREVALUE can be used to solve both DEGENERACY, and kk-CORE. For kk-CORE, the answer is direct. For DEGENERACY, it suffices to find the maximum core value, which can be done in O(D)O(D) additional rounds. Overall, among the problems in Definition 1, and letting aside the approximated variants, the easiest problem is kk-DEGENERATE, and the hardest is COREVALUE.

Our Results

We provide upper and lower bounds for the CONGEST complexities of the problems in Definition 1, and for related problems. We mostly provide lower bounds, except for one special case deserving specific attention.

Upper Bound

The sequential peeling algorithm can be implemented in CONGEST to solve COREVALUE (and therefore DEGENERACY, kk-CORE, and kk-DEGENERATE as well) in O(n)O(n) rounds on nn-node networks — see [14]. The resulting distributed algorithm may however take Ω(n)\Omega(n) rounds even on constant-diameter networks. Nevertheless, we show that solving 2-CORE, and therefore deciding 1-DEGENERATE as well, can actually be solved in O(D)O(D) rounds. This will contrast with our lower bounds for kk-DEGENERATE when k≥2k \ge2. Note that the dependence on DD for 2-CORE is optimal in the sense that any algorithm solving 2-CORE must run in Ω(D)\Omega(D) rounds.

Our algorithm relies on the fact that a node vv belongs to the 2-core if and only if it belongs to a cycle, or to a path whose endpoints belong to a cycle. This characterization allows us to implement an algorithm on top of a BFS tree through an upcast phase followed by a downcast phase. Local information is aggregated toward the root, and the resulting global information is then disseminated back to all nodes. Since both phases operate along a BFS tree, the overall number of rounds is bounded by O(D)O(D).

Lower Bounds

The lower bounds are the main results in the paper. In short, we provide a series of results indicating that the existence of a CONGEST algorithm for computing degeneracy in O~(n)\widetilde{O}(n) rounds on networks of diameter o(n)o(n) is unlikely, and that a round complexity O~(n)\widetilde{O}(\sqrt{n}) is in fact unconditionally impossible even in networks of diameter O(log⁡n)O(\log n). Our Ω~(n)\widetilde{\Omega}(n) lower bound for degeneracy is conditional: any sublinear-round algorithm would either imply a major breakthrough in complexity theory or require unusually expensive local computation, far beyond the computational resources —typically, LOGSPACE— sufficient for most known CONGEST algorithms. It is in fact difficult to envision how such additional local power could overcome the communication bottleneck.

Unconditional Lower Bounds Our first result uses the Set-Disjointness problem from communication complexity to obtain a lower bound of Ω~(n)\widetilde{\Omega}(\sqrt{n}) rounds for any CONGEST algorithm computing the degeneracy of the network. More specifically, we show that, under the CONGEST(BB) model, that is, under the general version of CONGEST in which every two neighbors can exchange BB-bit messages at each round, deciding 2-DEGENERATE on nn-node networks of diameter 2p+82p+8 requires Ω((npB)p/2p+1)\Omega\left(\left(\frac{n}{pB}\right)^{p/2p+1}\right) rounds. In particular, in CONGEST, deciding 2-DEGENERATE requires Ω~(n)\widetilde{\Omega}(\sqrt{n}) rounds even in networks of diameter O(log⁡n)O(\log n), and Ω~(n3)\widetilde{\Omega}(\sqrt[3]{n}) rounds in networks of constant diameter.

These lower bounds hold even for randomized Monte-Carlo algorithms that succeed with probability 2/32/3. In fact, they also hold for the approximation variant of the problem. Specifically, we show that, for any ε>0\varepsilon>0, (2−ε)(2-\varepsilon)-APPROXDEGENERACY requires Ω(ε2(nε2pB)p/2p+1)\Omega\left(\varepsilon^{2}\left(\frac{n\varepsilon^{2}}{pB}\right)^{p/2p+1}\right) rounds to be solved in nn-node networks of diameter O(p+1/ε)O(p+1/\varepsilon) under the CONGEST(BB) model. In particular, for every fixed ε\varepsilon, (2−ε)(2-\varepsilon)-APPROXDEGENERACY requires Ω~(n)\widetilde{\Omega}(\sqrt{n}) rounds in CONGEST even in networks of diameter O(log⁡n)O(\log n), and Ω~(n3)\widetilde{\Omega}(\sqrt[3]{n}) rounds in networks of constant diameter.

We also show that the techniques developed by Haeupler, Wajc, and Zuzic [28, 29] cannot derive a lower bound for DEGENERACY better than Ω~(n)\widetilde{\Omega}(\sqrt{n}), and that the techniques developed by Abboud et al. [1] cannot derive non-trivial lower bounds for DEGENERACY. (We can however show how to extend these latter techniques to get an Ω~(n3)\widetilde{\Omega}(\sqrt[3]{n})-round lower bound for DEGENERACY, by a reduction from the pointer chasing problem; Still, this bound is worse than our Ω~(n)\widetilde{\Omega}(\sqrt{n}) lower bound.)

Conditional Lower Bounds Our unconditional Ω~(n)\widetilde{\Omega}(\sqrt{n}) lower bound on the number of rounds demonstrates that there cannot exist super-efficient algorithms computing the degeneracy of networks (e.g., in polylog(n)(n) rounds). However, this bound does not prevent the existence of a sublinear algorithm, i.e., running in O(n1−ε)O(n^{1-\varepsilon}) rounds for some 0<ε≤1/20<\varepsilon\le1/2. We show that it is unlikely that such an algorithm exists.

Our second lower bound result depends on the computational capacity of individual nodes, that is, on the amount of local computation they can perform in each round. Specifically, we show that, on nn-node networks, if there exists a CONGEST algorithm solving 2-DEGENERATE in R(n)R(n) rounds with T(n)T(n) parallel computation time per round at each node (on a PRAM with poly(n)(n) processors), then 2-DEGENERATE can be solved by a PRAM algorithm that runs in time O~(R(n)⋅T(n))\widetilde{O}(R(n)\cdot T(n)) using poly(n)(n) processors.

A direct consequence of this theorem is that 2-Degenerate requires Ω(D+n1−ε)\Omega(D+n^{1-\varepsilon}) rounds in nn-node networks of diameter DD under the CONGEST model with O(nδ)O(n^\delta) parallel computation time per round at every node whenever ε>δ>0\varepsilon>\delta>0, unless the circuit value problem9 (CVP) admits a parallel polynomial speedup. As establishing such a speedup would be a breakthrough in complexity theory, our result shows that it is unlikely that a truly sublinear algorithm for degeneracy exists, or this would be at the cost of performing a huge amount of computation per round at some node. We stress the fact that our lower bound holds even in networks of constant maximum degree.

For illustrating the significance of our conditional lower bound, we note that most algorithms in CONGEST are frugal in terms of local computation, and many can actually be implemented in LOGSPACE. In contrast, a sequential computation time poly⁡(n)\operatorname{poly}(n) at every node in nn-node graphs of constant maximum degree Δ\Delta corresponds to exponential time with respect to the amount of information O(Δlog⁡n)O(\Delta\log n) received at each round by each node. Our result holds for computation power beyond LOGSPACE, up to O(nδ)O(n^\delta) parallel computation time per round at every node. As a consequence, developing efficient algorithms for Degeneracy in CONGEST would require exploiting the unlimited local computation power of this model, far beyond what is typically done.

Remark. Stated as is, our conditional lower bound applies only to deterministic algorithms. However, the randomized version of the conjecture, i.e., that CVP does not admit a randomized parallel speedup, has not been disproved. Our lower bound is thus likely to hold for randomized algorithms as well.

Beyond Degeneracy and k-Core Up to our knowledge, this paper is the first to explicitly establish connections between parallel complexity and CONGEST lower bounds. These connections apply not only to degeneracy and kk-core, but also to variants of these problems, as well as to other P-complete problems. Note that it was known [20] that such connections exist between the Congested Clique model and circuit complexity, which essentially hindered proving non-trivial lower bounds for the Congested Clique model.

More precisely, our conditional lower bound holds for the complexity in CONGEST of several P-complete graph problems, namely the ones with a reduction from CVP satisfying some restrictive conditions. As an important illustration, this is in particular the case for maximum flow (MaxFlow). As other examples, one can mention the resolution of problems playing an important role in CONGEST, such as (Δ+1)(\Delta+1)-coloring graphs of maximum degree Δ\Delta, or computing a maximal independent set, with the additional constraint of finding the smallest solution under some lexicographic ordering, referred to as LexCol and LexMIS. Our conditional Ω(n)\Omega(n) lower bound also applies to MaxFlow, LexCol, and LexMIS.

Related Work

The potential of parallelism to speed up polynomial-time sequential algorithms has been a subject of study for almost four decades [15]. Roughly speaking, a sequential algorithm with running time t(n)t(n) admits a polynomial parallel speedup if there exists a parallel algorithm that uses a polynomial number of processors and runs in time T(n)T(n), with t(n)/T(n)=Ω(nε)t(n)/T(n)=\Omega(n^\varepsilon) for some ε>0\varepsilon>0. Despite extensive efforts, the fundamental question of whether all problems admit a polynomial speedup remains open. Partial advances, however, shed light on this question. For instance, in the early 90s, Mak [37] showed that it is always possible to achieve a polynomial speedup, albeit with an exponential number of processors. Two decades later, Williams proved [51] that an O(log⁡n)O(\log n) speedup can be achieved on a log-cost RAM algorithm, when using a log-cost PRAM with a polynomial number of processors, and conjectured that this speedup might be improved to O(log⁡n⋅log⁡log⁡n)O(\log n \cdot\log\log n). Yet even such a modest improvement remains unproven. Whether CVP admits any polynomial parallel speedup also remains open.

There is a noticeable similarity between results on kk-core in distributed and parallel systems. With respect to parallel computation, Anderson and Mayr [4] showed that computing the kk-core is P-complete, that there exists a (2+ε)(2+\varepsilon)-approximation for kk-core in NC, and that no (2−ε)(2-\varepsilon)-approximation in NC exists unless P = NC. In the context of distributed systems, the study of core values was initiated in [42]. An O(log⁡n)O(\log n)-round (2+ε)(2+\varepsilon)-approximation algorithm for computing the core values in CONGEST was designed in [14], where it is also proved that any (2+ε)(2+\varepsilon)-approximation needs Ω(log⁡n)\Omega(\log n) rounds, and any (2−ε)(2-\varepsilon)-approximation needs Ω(D)\Omega(D) rounds. Our lower bounds for 2-DEGENERATE also hold for (2−ε)(2-\varepsilon)-approximation algorithms computing the core values, and are actually stronger. Several other works developed distributed algorithms for kk-core [2, 5, 27, 39]. However, these works are based on heuristics, with a focus on algorithms that run fast on real-world instances. As we show in this paper, obtaining an efficient distributed algorithm for kk-core on general instances is not feasible.

Several algorithms in CONGEST are parameterized by degeneracy, as for instance subgraph detection [32, 45], and their algorithms use the existing efficient (2+ε)(2+\varepsilon)-approximations for degeneracy. While these parameterized algorithms are efficient (in low degeneracy graphs), and while a (2+ε)(2+\varepsilon)-approximation is enough for their use case, the dependency on the computed approximation degeneracy dd of the actual degeneracy may be exponential, as in the 2O(kd)kk+O(log⁡n)2^{O(kd)}k^{k}+O(\log n) rounds for finding induced tree subgraphs on kk nodes [45]. Our results imply that it is unfortunately not possible to lower the exponent by achieving an approximation ratio better than 2 for the degeneracy.

In the framework of streaming algorithms, a single-pass algorithm that computes a (1+ε)(1+\varepsilon)-approximation for every core value using O~(n/ε2)\widetilde{O}(n/\varepsilon^{2}) space is presented in [22]. In contrast, any semi-streaming algorithm for exactly solving this problem requires Ω~(n1/3)\widetilde{\Omega}(n^{1/3}) passes [7]. Regarding dynamic graph algorithms, [16] established conditional lower bounds for the kk-core problem. Namely, assuming well-established conjectures, the kk-core problem requires Ω(m1−ε)\Omega(m^{1-\varepsilon}) time per update or query on a graph with mm edges. O’Brien and Sullivan [47] presented an algorithm that estimates the core value of every node vv based on local information within a ball of bounded radius centered at vv. The algorithm provides an asymptotic error bound for the core value estimation on Erdős–Rényi random graphs.

Preliminaries

CONGEST Model

The CONGEST(BB) model [48] is a classical model of distributed computation represented by a connected simple graph7^{7} G=(V,E)G=(V,E), where each node v∈Vv \in V executes the same algorithm in synchronous rounds, and the nodes collaborate to solve a graph problem defined on GG. Every node has an identifier, which is unique in the network. It is assumed that, in an nn-node network, each identifier can be stored in O(log⁡n)O(\log n) bits. Additionally, every node vv may receive an input. The goal is for each vertex to produce a predefined output based on the structure of the graph and the input of all nodes. In DEGENERACY, every node must eventually output the degeneracy of the graph, while in kk-CORE, it must output yes or no depending on whether it belongs to the kk-core of the network.

The defining feature of the CONGEST(BB) model is that computation proceeds as a sequence of synchronous rounds. In each round, every node sends a message to each of its neighbors, receives messages from all of its neighbors, and performs some local computation. The size of the messages is restricted to BB bits. Each node is allowed to perform an unlimited amount of local computation. Thus, the main computational cost is measured in terms of communication rounds. The standard CONGEST model corresponds to CONGEST(BB) with B=O(log⁡n)B = O(\log n), which allows each message to contain, for example, at most a constant number of node identifiers.

Remark. The LOCAL model is the same as CONGEST(∞\infty), that is, there are no restrictions on the size of the messages exchanged. In particular, every (computable) graph problem is solvable in O(D)O(D) rounds under the LOCAL model in networks of diameter DD, by gathering the whole graph at one node (e.g., the one with minimum identifier), computing the solution locally at this node, and broadcasting that solution back to all nodes. Such a trivial solution is not possible in CONGEST, as gathering the whole graph on a node may take Ω(n)\Omega(n) rounds in sparse or dense graphs.

PRAM, NC, and the Circuit Value Problem

A parallel random-access machine (parallel RAM, or PRAM for short) is a multiprocessor shared-memory abstract machine. In the so-called concurrent read exclusive write (CREW) PRAM, at each time step, each memory register can be read by multiple processors, or be written to by a single one. There are other variants of the PRAM model, which differ in how processors access the memory registers (such as EREW), but all of them are equivalent up to polylogarithmic factors in the running time, and polynomial factors in the number of processors. The class P is the set of all decision problems (or languages) decidable in polynomial time on a (sequential) RAM. The class NC is the set of all decision problems (or languages) decidable in polylogarithmic time on a PRAM with a polynomial number of processors.

One of the central problems that is complete for P under NC reductions is the circuit value problem (CVP). A (Boolean) circuit is a directed acyclic graph (DAG), with each node labeled from the set {0,1,AND,OR,NOT}\{0, 1, \mathrm{AND}, \mathrm{OR}, \mathrm{NOT}\}, and a specified output node. We refer to nodes and edges of the DAG as gates and wires, respectively. The output gate has out-degree 0, while 0- and 1-gates have in-degree 0. Gates with out-degree larger than 1 output the same value on all wires. The propagation of the values of the 0- and 1-gates throughout the AND-, OR- and NOT-gates results in a 0 or 1 value output at each gate. The circuit value is the output value of the output gate. The size of the circuit is its number of gates plus wires. The circuit value problem is the problem of, given a circuit, computing its value. A circuit is monotone if it does not have NOT-gates. We refer to CVP restricted to monotone circuits where input gates have out-degree 1, non-input non-output gates have in- and out-degree exactly 2, and the output gate has in-degree 2, as the monotone fan-in 2 fan-out 2 circuit value problem (M2CVP). It is known [26] that M2CVP, as CVP, is P-complete.

Flows, Lexicographic MIS and (Δ+1\Delta+1)-Coloring

Our lower bounds for degeneracy and kk-core also apply to other problems such as, prominently, computing maximum flows.

Maximum Flow

Let D=(V,A)D = (V,A) be a directed graph, let c:A→Nc : A \to\mathbb{N} be the arc capacities, and let ss and tt be the source and sink vertices, respectively. A flow in DD is a mapping f:A→Nf : A \to\mathbb{N}. A flow ff is feasible if f(e)≤c(e)f(e) \le c(e) for each arc e∈Ae \in A, and ∑wv∈Af(wv)=∑vw∈Af(vw)\sum_{w v \in A} f(wv) = \sum_{v w \in A} f(vw) for each u∈V∖{s,t}u \in V \setminus\{s,t\}. The MAXFLOW problem asks to compute a feasible flow ff that maximizes ∑sv∈Af(sv)\sum_{sv \in A} f(sv). In CONGEST, each node receives the orientation and capacities of its arcs, and must output the value of a (feasible and maximum) flow for each arc incident to it.

Lexicographic Variants of LCL Problems

Other problems impacted by our results include lexicographic variants of standard locally checkable labeling problems such as maximal independent set and (Δ+1\Delta+1)-coloring. The study of such problems is standard in the context of parallel complexity [26]. In all these variants, we assume that every node vv of the graph G=(V,E)G = (V,E) is given a number ℓ(v)∈N\ell(v) \in\mathbb{N} as input, which is assumed to be unique.

  • Recall that an independent set in GG is a set of pairwise non-adjacent vertices of GG, and that an independent set is maximal if no vertex can be added to it while maintaining the independent set property. Let I={v1,…,vr}I = \{v_1, \ldots, v_r\} be a maximal independent set with ℓ(v1)<⋯<ℓ(vr)\ell(v_1) < \cdots< \ell(v_r). The ordered sequence (ℓ(v1),…,ℓ(vr))(\ell(v_1), \ldots, \ell(v_r)) is called the signature of II. The LexMIS problem asks to compute the maximal independent set of GG that has the smallest signature, where signatures are lexicographically ordered as words on the alphabet N\mathbb{N}. In CONGEST, each node must output 1 if it is in the MIS, and 0 otherwise.

  • A kk-coloring of GG is an assignment c:V→{1,…,k}c : V \to\{1, \ldots, k\} such that c(u)≠c(v)c(u) \ne c(v) for each uv∈Euv \in E. The lexicographic variant of (Δ+1)(\Delta+ 1)-coloring is defined similarly, where Δ\Delta denotes the maximum degree of GG. Let V={v1,…,vn}V = \{v_1, \ldots, v_n\} with ℓ(v1)<⋯<ℓ(vn)\ell(v_1) < \cdots< \ell(v_n). Given a (Δ+1)(\Delta+ 1)-coloring cc of GG, the ordered sequence (c(v1),…,c(vn))(c(v_1), \ldots, c(v_n)) is called the signature of the coloring cc. The LexCol problem asks to compute the (Δ+1)(\Delta+ 1)-coloring of GG that has the smallest signature, when signatures are compared lexicographically as words on the alphabet {1,…,Δ+1}\{1, \ldots, \Delta+ 1\}. In CONGEST, each node must output its color.

Both LexMIS and LexCol have sequential greedy algorithms in which one decides, node by node, in increasing order of their labels, whether they belong to the maximal independent set, or which color they should be given. We will show that there is no efficient way to parallelize or distribute this greedy algorithm.

Unconditional Lower Bounds

We start by providing unconditional lower bounds based on the framework of “moving cuts” designed by Das Sarma et al. [18]. We begin the presentation by considering the exact variant of degeneracy (deciding 2-Degenerate), and then show how to extend the bound to the approximated variant of degeneracy.

Lower Bound for Deciding Degeneracy 2

Let us define a graph family used for establishing the lower bound. For integers p≥1p \ge1, q≥1q \ge1, and d≥2d \ge2, let G(q,d,p)G(q, d, p) be the graph consisting of qq paths, each with dpd^p nodes, plus a complete dd-ary tree TT of depth pp and dpd^p leaves. The iith leaf of TT is connected to the iith vertex in each of the qq paths. We denote by ss and rr the first and last leaves of TT. See Figure 1 for an illustration. The graph G(q,d,p)G(q, d, p) has Θ(q⋅dp)\Theta(q \cdot d^p) nodes, and diameter 2p+22p + 2.

Figure 1. The graph G(q,d,p)G(q,d,p) for q=3q = 3, d=2d = 2, and p=2p = 2, that is, G(3,2,2)G(3,2,2).

Our lower bound in CONGEST follows from the lower bound for the set-disjointness problem in communication complexity. Given an integer q≥1q \ge1, the qq-disjointness problem in G(q,d,p)G(q, d, p), denoted by Disj⁡q(s,r)\operatorname{Disj}^{q}(s,r), is defined as follows. Nodes ss and rr are respectively given inputs x∈{0,1}qx \in\{0,1\}^{q} and y∈{0,1}qy \in\{0,1\}^{q}. The goal is for ss and rr to decide whether xx and yy are disjoint, that is, whether min⁡{xi,yi}=0\min\{x_i,y_i\} = 0 for all i∈{1,…,q}i \in\{1, \ldots, q\}. Both nodes must accept if xx and yy are disjoint, and both of them must reject otherwise. Our lower bound is based on the following result.

Lemma 2 ([18]). For any p≥1p \ge1, and d≥2d \ge2, DISJ⁡q(s,r)\operatorname{DISJ}^{q}(s,r) on G(q,d,p)G(q,d,p) with q=dp+1pBq = d^{p+1}pB requires Ω(dp)\Omega(d^{p}) rounds to be solved in CONGEST⁡(B)\operatorname{CONGEST}(B), even by a randomized Monte-Carlo algorithm succeeding with probability 2/32/3.

To obtain a lower bound for 2-Degenerate, we show that any algorithm for this problem can be used to solve DISJ⁡q(s,r)\operatorname{DISJ}^{q}(s,r) on G(q,d,p)G(q,d,p). This will require to modify the network G(q,d,p)G(q,d,p), but we shall later argue how our modifications can be simulated by the nodes of the original G(q,d,p)G(q,d,p). Our construction is based on the following graph family. For any integers q,p≥1q,p \ge1, any binary strings x,y∈{0,1}qx,y \in\{0,1\}^{q}, and any integer d≥2d \ge2, the graph H(x,y,q,d,p)H(x,y,q,d,p) is obtained by modifying G(q,d,p)G(q,d,p). The construction uses the gadget depicted on Figure 2, referred to as the flyswatter gadget. Copies of this gadget are attached to vertices of G(q,d,p)G(q,d,p) according to the following rules.

Figure 2. The flyswatter gadget. If the gadget is attached to a node vv in H(x,y,q,d,p)H(x,y,q,d,p), then the node vv is the node depicted by the dotted circle on the figure.

  • For every i∈[q]i \in[q], if xi=1x_i = 1 then attach a flyswatter to the first node of the iith path.

  • For every i∈[q]i \in[q], if yi=1y_i = 1 then attach a flyswatter to the last node of the iith path.

  • Attach a flyswatter to each leaf of the tree TT in G(q,d,p)G(q,d,p), as well as to its root.

As the number of nodes in H(x,y,q,d,p)H(x,y,q,d,p) is at most a constant factor larger than the number of nodes in G(q,d,p)G(q,d,p), and as its diameter increases by at most twice the diameter of the flyswatter, the following holds:

Observation 3. H(x,y,q,d,p)H(x,y,q,d,p) has Θ(qdp)\Theta(qd^{p}) nodes, and diameter 2p+82p+8.

The way the flyswatters are attached to G(q,d,p)G(q,d,p) as a function of xx and yy enables one to relate the degeneracy of H(x,y,q,d,p)H(x,y,q,d,p) to the truth value of the disjointness of xx and yy.

Lemma 4. H(x,y,q,d,p)H(x,y,q,d,p) is 2-degenerate if and only if xx and yy are disjoint.

Proof. Suppose first that H=H(x,y,q,d,p)H = H(x,y,q,d,p) is 2-degenerate, i.e., every subgraph of HH has a vertex of degree at most 2. Let HiH_i be the subgraph of HH containing its iith path, the tree TT of G(q,d,p)G(q,d,p), and all flyswatters attached to those vertices. Note that all internal vertices of the iith path, all the vertices in TT, and all vertices in the flyswatters have degree at least 3 in HiH_i, independently of the values of xx and yy. For every i∈{1,…,q}i \in\{1,\ldots,q\}, since HH is 2-degenerate, there must be a vertex of HiH_i with degree at most 2, which implies that at least one of the two endpoints of the iith path is not connected to a flyswatter. It follows that xi=0x_i = 0 or yi=0y_i = 0, and thus xx and yy are disjoint.

Let us now suppose that H=H(x,y,q,d,p)H = H(x,y,q,d,p) is not 2-degenerate, meaning that HH has a nonempty 3-core H′H'. A flyswatter can have either all its vertices in the 3-core H′H', or none of them. That is, a flyswatter belongs to H′H' if and only if it is attached to a vertex that belongs to H′H'. Also, H′H' cannot be completely contained in the tree TT. It follows that H′H' must contain some vertex from at least one of the qq paths, as otherwise H′H' would be empty. A consequence of the fact that H′H' contains at least one vertex vv from one of the paths is that H′H' must contain all the neighbors of vv because the vertices in the paths have degree at most 3 in H(x,y,q,d,p)H(x,y,q,d,p). It follows that H′H' must actually contain a complete path, say the iith path, for some i∈{1,…,q}i \in\{1,\ldots,q\}. In particular, the endpoints of that path must have degree 3, which implies that they are both attached to a flyswatter. This means that xi=yi=1x_i = y_i = 1, and thus xx and yy are not disjoint. □

Now, we show how to transform an algorithm for 2-DEGENERATE into an algorithm for DISJq(s,r)^{q}(s,r), while controlling its round complexity.

Lemma 5. If there exists an algorithm A\mathcal{A} solving 2-DEGENERATE on nn-node networks of diameter 2p+82p+8 in R(n)=O(n)R(n)=O(n) rounds under CONGEST(B)(B), then there exists an algorithm B\mathcal{B} solving DISJq(s,r)^{q}(s,r) on G(q,d,p)G(q,d,p) in O(R(q⋅dp)+p)O(R(q\cdot d^{p})+p) rounds under CONGEST(B)(B). Moreover, if A\mathcal{A} is a randomized Monte Carlo algorithm succeeding with probability at least 2/32/3, then so is B\mathcal{B}.

Proof. Suppose that there is an algorithm A\mathcal{A} for 2-DEGENERATE as in the statement. We describe an algorithm B\mathcal{B} for DISJq(s,r)^{q}(s,r) on G(q,d,p)G(q,d,p). In the first round of B\mathcal{B}, for each i∈[q]i\in[q], node ss sends xix_i to the first node of the iith path, and node rr sends yiy_i to the last node of the iith path.

At this point, every node has enough information to determine whether it is attached to a flyswatter gadget in the construction of H(x,y,q,d,p)H(x,y,q,d,p), and so can simulate the virtual execution of A\mathcal{A} on H(x,y,q,d,p)H(x,y,q,d,p) in the actual network G(q,d,p)G(q,d,p). In particular, any node vv that is attached to a flyswatter gadget locally simulates the states and the exchanged messages for all (virtual) nodes in that gadget. Since the only edge leaving a flyswatter gadget connects to the node that is simulating that gadget, the simulation does not require any additional communication over the edges of G(q,d,p)G(q,d,p). From the second round, B\mathcal{B} is thus the mere simulation of A\mathcal{A} on the virtual network H(x,y,q,d,p)H(x,y,q,d,p).

At the end of the simulation, the nodes output the result of A\mathcal{A}, i.e., whether H(x,y,q,d,p)H(x,y,q,d,p) is 2-degenerate or not. More specifically, if H(x,y,q,d,p)H(x,y,q,d,p) is 2-degenerate then all nodes accept, and if H(x,y,q,d,p)H(x,y,q,d,p) is not 2-degenerate, then at least one node rejects. To guarantee that both rr and ss reject in case H(x,y,q,d,p)H(x,y,q,d,p) is not 2-degenerate, any rejecting node floods its opinion throughout the network, in diameter rounds. By Lemma 4, this algorithm B\mathcal{B} correctly computes whether xx and yy are disjoint.

As far as the round complexity of B\mathcal{B} is concerned, note that its first round communicates at most one bit per edge, so this round is valid in CONGEST(B)(B) for any B≥1B\geq1. The simulation in G(q,d,p)G(q,d,p) of the execution of A\mathcal{A} on H(x,y,q,d,p)H(x,y,q,d,p) takes 1+R(Θ(q⋅dp))1+R(\Theta(q\cdot d^{p})) rounds because H(x,y,q,d,p)H(x,y,q,d,p) has Θ(q⋅dp)\Theta(q\cdot d^{p}) nodes (cf. Observation 3). By Observation 3, the final flooding consumes O(p)O(p) additional rounds. Since R(n)=O(n)R(n)=O(n), we have R(O(N))=O(R(N))R(O(N))=O(R(N)) for any NN, implying that B\mathcal{B} takes O(R(q⋅dp)+p)O(R(q\cdot d^{p})+p) rounds. □

Theorem 6. For any p≥1p\geq1, deciding 2-DEGENERATE on nn-node networks of diameter 2p+82p+8 requires Ω((npB)p/(2p+1))\Omega\left(\left(\frac{n}{pB}\right)^{p/(2p+1)}\right) rounds in the CONGEST(B)(B) model. This holds even for randomized Monte-Carlo algorithms succeeding with probability at least 2/32/3.

Proof. Suppose that there is a randomized CONGEST(B)(B) algorithm for 2-DEGENERATE on nn-node networks running in R(n)R(n) rounds, where R(n)=O(n)R(n)=O(n). By Lemma 5, there is a randomized algorithm for DISJq(s,r)^{q}(s,r) on the network G(q,d,p)G(q,d,p) running in O(R(q⋅dp))O(R(q\cdot d^{p})) rounds. By Lemma 2, we obtain R(q⋅dp)=Ω(dp)R(q\cdot d^{p})=\Omega(d^{p}), when q=dp+1pBq=d^{p+1}pB. Since the number of nodes in the network H(x,y,q,d,p)H(x,y,q,d,p) is n=Θ(q⋅dp)=Θ(d2p+1pB)n=\Theta(q\cdot d^{p})=\Theta(d^{2p+1}pB), and since R(n)=Ω(dp)R(n)=\Omega(d^{p}), expressing dpd^{p} in terms of nn yields R(n)=Ω((n/pB)p/(2p+1))R(n)=\Omega\left((n/pB)^{p/(2p+1)}\right), as claimed. □

Corollary 7. Deciding 2-DEGENERATE on nn-node networks of diameter O(log⁡n)O(\log n) requires Ω(n/log⁡2n)\Omega\left(\sqrt{n/\log^{2}n}\right) rounds in CONGEST, and deciding 2-DEGENERATE on nn-node networks of diameter 1010 requires Ω(n/log⁡n3)\Omega\left(\sqrt[3]{n/\log n}\right) rounds in CONGEST.

Lower Bound for Approximate Degeneracy

We now show that even approximating the degeneracy of a graph within a multiplicative factor smaller than 2 is hard. To do that, we introduce a graph Hk(x,y,q,d,p)H_k(x,y,q,d,p) for every k≥2k\geq2 and x,y∈{0,1}qx,y\in\{0,1\}^{q}. Our construction guarantees that the degeneracy of Hk(x,y,q,d,p)H_k(x,y,q,d,p) changes by a large factor depending on whether xx and yy are disjoint, which allows us to use any (2−ε)(2-\varepsilon)-approximation for the degeneracy to solve Disj⁡q(s,r)\operatorname{Disj}^{q}(s,r), from which a similar lower bound as the one given in Theorem 6 for 2-Degenerate can be obtained.

A stable graph is a graph with no edges (every vertex has degree 0). We denote by SkS_k the stable graph on k≥1k \ge1 vertices. We define Hk(x,y,q,d,p)H_k(x,y,q,d,p) as the graph obtained from G(q,d,p)G(q,d,p) by using the gadget depicted in Figure 3 referred to as the fishnet gadget FkF_k. This gadget graph consists of k+2k+2 copies of SkS_k connected in sequence (i.e., every vertex of the iith copy is connected to all vertices of the (i−1)(i-1)th copy, and to all vertices of the (i+1)(i+1)th copy). Moreover, the jjth node of the first copy of SkS_k is connected to the jjth node of all the k+1k+1 other copies. The connection of a fishnet gadget to the graph G(q,d,p)G(q,d,p) is achieved via the kk nodes of the last copy of SkS_k (see Figure 3).

Figure 3. The fishnet gadget FkF_k for k=3k = 3, connected to S3S_3 whose vertices are the three to the right, represented by dotted circles.

The graph Hk(x,y,q,d,p)H_k(x,y,q,d,p) is obtained from G(q,d,p)G(q,d,p) as follows:

  • Each vertex uu in a path of G(q,d,p)G(q,d,p) is replaced by a copy SkuS_k^u of the stable graph SkS_k.

  • Each path edge uvuv is replaced by k2k^2 edges connecting all vertices of SkuS_k^u to SkvS_k^v.

  • Each edge ℓu\ell u from a leaf ℓ\ell to a path vertex uu is replaced by kk edges connecting ℓ\ell to all vertices in SkuS_k^u.

  • For each i∈[q]i \in[q], if xi=1x_i = 1 then a fishnet FkF_k is attached to the first copy of SkS_k in the iith path, and if yi=1y_i = 1 then a fishnet is attached to the last copy of SkS_k in the iith path.

Figure 4 provides an example of Hk(x,y,q,d,p)H_k(x,y,q,d,p).

Figure 4. The graph Hk(x,y,q,d,p)H_k(x,y,q,d,p) for k=3k=3, x=(101)x=(101), y=(011)y=(011), q=3q=3, d=2d=2, and p=2p=2, built from G(3,2,2)G(3,2,2) shown in Figure 2.

The interest of the graph Hk(x,y,q,d,p)H_k(x,y,q,d,p) is that its degeneracy differs a lot depending on whether xx and yy are disjoint.

Lemma 8. The degeneracy dkd_k of Hk(x,y,q,d,p)H_k(x,y,q,d,p) satisfies dk≤k+1d_k \le k+1 if xx and yy are disjoint, and dk≥2kd_k \ge2k otherwise.

Proof. Let us first assume that xx and yy are disjoint, and let us assume for the purpose of contradiction that Hk(x,y,q,d,p)H_k(x,y,q,d,p) contains a nonempty (k+2)(k+2)-core H′H'. Note that H′H' cannot be contained entirely in a fishnet FkF_k because FkF_k has minimum degree ≤k+1\le k+1 if it is not attached to the graph G(q,d,p)G(q,d,p). Similarly H′H' cannot be entirely contained in the tree TT of G(q,d,p)G(q,d,p). As a consequence, H′H' must contain a vertex uu of some copy of SkS_k in some path. Let us say that uu belongs to the jjth copy of SkS_k in the iith path, for some i∈[q]i \in[q] and j∈[dp]j \in[d^p]. On the one hand, node uu has at least k+2k+2 neighbors in H′H'. On the other hand, in Hk(x,y,q,d,p)H_k(x,y,q,d,p), node uu has one incident edge connecting it to the tree TT, at most kk neighbors to its left11 and, analogously, at most kk neighbors to its right. It follows that, in H′H', uu must have at least one neighbor to each side. Repeating this argument yields a contradiction, since xi=0x_i = 0 or yi=0y_i = 0, meaning at least one of the endpoints of the iith path is not attached to a fishnet. As a consequence, the (k+2)(k+2)-core of Hk(x,y,q,d,p)H_k(x,y,q,d,p) is empty, and thus dk≤k+1d_k \le k+1.

Conversely, if xx and yy are not disjoint, then there exists i∈[q]i \in[q] such that xi=yi=1x_i=y_i=1. Let H′H' be the subgraph of Hk(x,y,q,d,p)H_k(x,y,q,d,p) consisting of all copies of SkS_k in the iith path, and the fishnets attached to its first and last copies of SkS_k. Note that H′H' has minimum degree 2k2k because, when connected to Hk(x,y,q,d,p)H_k(x,y,q,d,p), a fishnet has minimum degree 2k2k. This implies that the 2k2k-core of Hk(x,y,q,d,p)H_k(x,y,q,d,p) is not empty, and thus dk≥2kd_k \ge2k.

Lemma 9. If there exists an algorithm A\mathcal{A} solving (2−ε)(2-\varepsilon)-ApproxDegeneracy on nn-node networks with diameter O(p+1/ε)O(p+1/\varepsilon) in R(n)=O(n)R(n)=O(n) rounds under CONGEST(B), then there exists an algorithm B\mathcal{B} solving Disjqd(s,r)_q^d(s,r) on G(q,d,p)G(q,d,p) in O(1ε2R(qε2dp))O\left(\frac{1}{\varepsilon^2}R\left(\frac{q}{\varepsilon^2}d^p\right)\right) rounds under CONGEST(B). Moreover, if A\mathcal{A} is a randomized Monte-Carlo algorithm succeeding with probability 2/32/3, then so is B\mathcal{B}.

Proof. Suppose that there is an algorithm A\mathcal{A} for (2−ε)(2-\varepsilon)-ApproxDegeneracy as in the statement. For designing B\mathcal{B}, let k=Θ(1/ε)k=\Theta(1/\varepsilon) to be specified later. We proceed as in the proof of Lemma 5, merely using Hk(x,y,q,d,p)H_k(x,y,q,d,p) instead of H(x,y,q,d,p)H(x,y,q,d,p). In particular, the information needed to determine how to simulate Hk(x,y,q,d,p)H_k(x,y,q,d,p), which depends only on xx and yy can be sent by rr and ss to their neighbors in a single round. Furthermore, the nodes can simulate the virtual graph Hk(x,y,q,d,p)H_k(x,y,q,d,p) on the actual network G(q,d,p)G(q,d,p). Specifically, each vertex of G(q,d,p)G(q,d,p) needs to simulate O(k2)O(k^2) nodes, and each edge of G(q,d,p)G(q,d,p) is mapped to O(k2)O(k^2) edges of Hk(x,y,q,d,p)H_k(x,y,q,d,p). So, each round of A\mathcal{A} can be simulated in O(k2)O(k^2) rounds of B\mathcal{B}. Note that Hk(x,y,q,d,p)H_k(x,y,q,d,p) has O(k2q+kqdp)O(k^2q+kqd^p) nodes (and O(k2qdp)O(k^2qd^p) edges), and therefore it has O(k2qdp)O(k^2qd^p) nodes. Also, it has diameter O(p+k)O(p+k). Therefore, the total running time of B\mathcal{B} is O(k2R(k2qdp))=O(1ε2R(qε2dp))O(k^2R(k^2qd^p))=O\left(\frac{1}{\varepsilon^2}R\left(\frac{q}{\varepsilon^2}d^p\right)\right).

An appropriate choice of kk is ⌊2−εε⌋+1\left\lfloor\frac{2-\varepsilon}{\varepsilon}\right\rfloor+1 because this choice guarantees that 2kk+1>2−ε\frac{2k}{k+1}>2-\varepsilon. Let cvc_v be any (2−ε)(2-\varepsilon)-approximation to the degeneracy dkd_k of Hk(x,y,q,d,p)H_k(x,y,q,d,p) computed by any node, that is, dk≤cv≤(2−ε)dk<2kk+1dkd_k\le c_v\le(2-\varepsilon)d_k<\frac{2k}{k+1}d_k. By Lemma 8, if xx and yy are not disjoint then dk≥2kd_k\ge2k, implying cv≥dk≥2kc_v\ge d_k\ge2k. If xx and yy are disjoint, and if dk≤k+1d_k\le k+1, then 2k≥2kk+1dk>cv2k\ge\frac{2k}{k+1}d_k>c_v. Thus if cv<2kc_v<2k then xx and yy are disjoint, and otherwise they are not, proving the correctness of B\mathcal{B}. □\square

Theorem 10. Let ε>0\varepsilon> 0, B≥1B \ge1, and p≥1p \ge1. Solving (2−ε)(2-\varepsilon)-ApproxDegeneracy on nn-node networks with diameter O(p+1/ε)O(p+1/\varepsilon) requires Ω(ε2(nε2pB)p2p+1)\Omega\left(\varepsilon^2\left(\frac{n\varepsilon^2}{pB}\right)^{\frac{p}{2p+1}}\right) rounds in the CONGEST(B)(B) model. This holds even for randomized Monte-Carlo algorithms succeeding with probability 2/32/3.

Proof. Suppose that there is a (randomized) algorithm solving (2−ε)(2-\varepsilon)-ApproxDegeneracy on nn-node networks in R(n)=O(n)R(n)=O(n) rounds. By Lemma 9, there is a (randomized) algorithm for Disjq(s,r)^q(s,r) on G(q,d,p)G(q,d,p) running in O(1ε2R(qε2dp))O\left(\frac{1}{\varepsilon^2}R\left(\frac{q}{\varepsilon^2}d^p\right)\right) rounds. By Lemma 2, we get R(qε2dp)=Ω(ε2dp)R\left(\frac{q}{\varepsilon^2}d^p\right)=\Omega(\varepsilon^2d^p), when q=dp+1pBq=d^{p+1}pB. Now, for the appropriate k=Θ(1/ε)k=\Theta(1/\varepsilon), the number of nodes in Hk(x,y,q,d,p)H_k(x,y,q,d,p) is n=O(k2qdp)=O(1ε2d2p+1pB)n=O(k^2qd^p)=O\left(\frac{1}{\varepsilon^2}d^{2p+1}pB\right). As R(n)=Ω(ε2dp)R(n)=\Omega(\varepsilon^2d^p), expressing dpd^p in terms of nn yields R(n)=Ω(ε2(nε2pB)p2p+1)R(n)=\Omega\left(\varepsilon^2\left(\frac{n\varepsilon^2}{pB}\right)^{\frac{p}{2p+1}}\right), as claimed. □\square

Corollary 11. For any fixed1 ε>0\varepsilon>0, solving (2−ε)(2-\varepsilon)-ApproxDegeneracy on nn-node networks of diameter O(log⁡n)O(\log n) requires Ω(n/log⁡2n)\Omega\left(\sqrt{n/\log^2 n}\right) rounds in CONGEST, and solving (2−ε)(2-\varepsilon)-ApproxDegeneracy on nn-node networks with constant diameter requires Ω(n/log⁡n3)\Omega\left(\sqrt[3]{n/\log n}\right) rounds.

Conditional Lower Bounds

Based on the lower bounds from Section 3, one might be tempted to design an O(n)O(\sqrt{n}), or even an O(n0.99)O(n^{0.99})-round algorithm for degeneracy in CONGEST. However, in this section, we show that, under modest restrictions, the existence of such an algorithm would imply major breakthroughs in parallel complexity theory.

Recall that a sequential algorithm A\mathcal{A} running in time t(n)=Ω(n)t(n)=\Omega(n) on inputs of size nn admits a polynomial parallel speedup [34] if there exist ε>0\varepsilon>0 and a PRAM algorithm B\mathcal{B} that implements A\mathcal{A} so that B\mathcal{B} runs in time T(n)T(n) using polynomially many processors, where t(n)/T(n)=Ω(nε)t(n)/T(n)=\Omega(n^\varepsilon). We relate the difficulty of solving the degeneracy problem in CONGEST with the difficulty of solving its decision version in parallel, for which many hardness results are known. In particular, the trivial sequential peeling algorithm for degeneracy takes O(n)O(n) time. Moreover, the problem is P-complete, that is, a polylog⁡(n)\operatorname{polylog}(n) time parallel algorithm is unlikely to exist. In fact, no O(n1−ε)O(n^{1-\varepsilon}) time parallel algorithm is known, for any ε>0\varepsilon>0, that is, degeneracy is not known to admit a polynomial parallel speedup. The same is the case for the aforementioned circuit value problem (CVP). We refer the reader to [26] for an in-depth discussion on P-completeness and parallelization.

Simulation Lemma

An R(n)R(n)-round CONGEST algorithm has local parallel time T(n)T(n) if it terminates in at most R(n)R(n) rounds and, at every node, and at every round, the node runs in time T(n)T(n) using poly⁡(n)\operatorname{poly}(n) processors on a PRAM for computing its new states and the messages to be sent. Let π\pi be a decision problem in graphs (e.g., 2-Degenerate). For solving π\pi in CONGEST, each node must output accept or reject for the problem, with global interpretation being that all nodes must accept if and only if π\pi holds. In the PRAM model the algorithm must simply accept or reject, according to whether π\pi holds or not.

Lemma 12. Let G\mathcal{G} be a class of graphs, and let π\pi be a decision problem in graphs. If there exists a CONGEST algorithm for π\pi in G\mathcal{G}, running on nn-node graphs in R(n)R(n) rounds, with T(n)T(n) local parallel computation time in the PRAM model, then there exists a PRAM algorithm for π\pi in G\mathcal{G} that runs in O~(R(n)⋅T(n))\widetilde{O}(R(n)\cdot T(n)) time using poly⁡(n)\operatorname{poly}(n) processors.

Proof. Let A\mathcal{A} be a CONGEST algorithm for π\pi in G\mathcal{G}, as in the statement. For sufficiently large nn, there exists a constant c>0c>0 such that, when running on an nn-node network, each node uses at most ncn^c processors. We split each round of A\mathcal{A} into two phases: computation, and communication. At the beginning of round tt, each node uu is in a memory state suts_u^t, and holds a list of messages Iut={mwut:w∈N(u)}I_u^t = \{m_{wu}^t : w \in N(u)\} received from its neighbors. Initially, all nodes are in the same empty memory state, and all lists of messages are empty. In the computation phase of round tt, node uu uses suts_u^t and IutI_u^t for computing a set of messages Out={muwt+1:w∈N(u)}O_u^t = \{m_{uw}^{t+1} : w \in N(u)\}, to be sent to its neighbors, and updates its memory state from suts_u^t to sut+1s_u^{t+1}. In the communication phase, the messages are delivered.

We define the desired PRAM algorithm B\mathcal{B} as follows. Let G∈GG \in\mathcal{G} be an nn-node instance of π\pi. Algorithm B\mathcal{B} stores suts_u^t, IutI_u^t, and OutO_u^t, and uses ncn^c processors for each node uu of GG. In addition, B\mathcal{B} uses n2n^2 other processors, for simulating the communication phase of A\mathcal{A}.

  • During the computation phase of round tt, B\mathcal{B} emulates (in parallel) the local computation of the CONGEST algorithm A\mathcal{A}. Each node uu, starting from the memory state suts_u^t, and using the incoming messages in IutI_u^t, computes OutO_u^t and sut+1s_u^{t+1} in T(n)T(n) time using its ncn^c processors. The PRAM algorithm B\mathcal{B} uses n⋅ncn \cdot n^c processors for simulating this phase.

  • During the communication phase of round tt, processor PuwP_{uw} overwrites muwtm_{uw}^t from IwtI_w^t with muwt+1m_{uw}^{t+1}, which takes O(log⁡n)O(\log n) time. Overall, this process transforms the stored IwtI_w^t into Iwt+1I_w^{t+1} for all ww. After this, B\mathcal{B} is ready to start the simulation of round t+1t+1 of the CONGEST algorithm A\mathcal{A}.

At the end of the simulation (i.e., when all nodes have terminated), B\mathcal{B} checks the output of each node, and accepts if and only if all nodes have accepted. This operation can be performed by B\mathcal{B} in O(log⁡n)O(\log n) time. In total, B\mathcal{B} uses nc+1+n2=poly⁡(n)n^{c+1} + n^2 = \operatorname{poly}(n) processors, and takes O~(T(n))\widetilde{O}(T(n)) time to (1) simulate each computation phase, (2) deliver the messages in each communication phase, and (3) check whether all nodes in the network have terminated the execution of A\mathcal{A}. It follows that π\pi in G\mathcal{G} admits a PRAM algorithm that, on nn-node graphs from G\mathcal{G}, runs in O~(R(n)⋅T(n))\widetilde{O}(R(n) \cdot T(n)) time using poly⁡(n)\operatorname{poly}(n) processors. □\square

As a consequence, the existence of a “fast” algorithm for π\pi in CONGEST implies the existence of a “fast” PRAM algorithm for π\pi. This fact allows us to translate known hardness results about degeneracy from the parallel computing context to CONGEST. This is what we do next.

Conditional Lower Bound for 2-Degenerate

Let π1\pi_1 and π2\pi_2 be two graph decision problems. We say π1\pi_1 has a quasi-linear NC-reduction to π2\pi_2, denoted by π1≤quasiNCπ2\pi_1 \leq_{\mathrm{quasi}}^{\mathrm{NC}} \pi_2, if there is a function ff from the set of graphs to the set of graphs such that, for every graph GG,

  • π1\pi_1 accepts GG if and only if π2\pi_2 accepts f(G)f(G),

  • ff is computable in NC,

  • ∣E(f(G))∣=O~(∣E(G)∣)|E(f(G))| = \widetilde{O}(|E(G)|), and

  • D(f(G))=O~(D(G))D(f(G)) = \widetilde{O}(D(G)), where D(H)D(H) denotes the diameter of graph HH.

Lemma 13. Let π\pi be a decision problem such that CVP≤quasiNCπ\mathrm{CVP} \leq_{\mathrm{quasi}}^{\mathrm{NC}} \pi. Unless CVP admits a polynomial parallel speedup, it holds that, for every ε∈(0,1)\varepsilon\in(0,1) and δ∈(0,ε)\delta\in(0,\varepsilon), π\pi does not admit a CONGEST algorithm running in O(n1−ε)O(n^{1-\varepsilon}) rounds with O(nδ)O(n^\delta) local parallel computation time in nn-node networks of diameter O~(1)\widetilde{O}(1).

Proof. Let us assume that there exists a CONGEST algorithm for π\pi as in the statement. Then, by Lemma 12, there exists a PRAM algorithm A\mathcal{A} for π\pi that runs in O~(n1−ε⋅nδ)=O~(n1−ε+δ)\widetilde{O}(n^{1-\varepsilon} \cdot n^\delta) = \widetilde{O}(n^{1-\varepsilon+\delta}) time using poly⁡(n)\operatorname{poly}(n) processors. Consider any instance CC of size nn for CVP, and modify it as follows. First, remove all pairs of consecutive NOT gates. Second, add a 0-gate connected to all OR-gates, and add a 1-gate connected to all AND-gates. The resulting circuit has size O(n)O(n), and constant diameter. Moreover, it has the same circuit value. Using the reduction from CVP to π\pi, one can in polylog⁡(n)\operatorname{polylog}(n) time construct an O~(n)\widetilde{O}(n)-node graph GCG_C of diameter polylog⁡(n)\operatorname{polylog}(n) that is an instance of π\pi such that π\pi accepts GCG_C if and only if the circuit value of CC is 1. One can solve the instance GCG_C with the PRAM algorithm A\mathcal{A}, which runs in O~(n1−ε+δ)\widetilde{O}(n^{1-\varepsilon+\delta}) time using poly⁡(n)\operatorname{poly}(n) processors. This implies that CVP admits a polynomial parallel speedup, as 1−ε+δ<11-\varepsilon+\delta<1.

Theorem 14. Let ε∈(0,1)\varepsilon\in(0,1) and δ∈(0,ε)\delta\in(0,\varepsilon). Unless CVP admits a polynomial parallel speedup, 2-Degenerate does not admit a CONGEST algorithm running in O(n1−ε)O(n^{1-\varepsilon}) rounds with O(nδ)O(n^\delta) local parallel computation time on nn-node networks, even on graphs of maximum degree 4 and diameter O(log⁡n)O(\log n).

Proof. Consider the monotone fan-in 2 fan-out 2 restriction to the circuit value problem, referred to as M2CVP. From any instance CC of CVP, one can construct an instance C′C' of M2CVP by applying the standard reduction that removes all NOT gates, and uses balanced binary trees to decrease the maximum out- and in-degree to 2 (see [26 Theorem 6.2.3]). If CC has size nn and diameter DD, then C′C' has size O(n)O(n) and diameter O(Dlog⁡n)O(D\log n). Then, we use the reduction from M2CVP to 2-Degenerate from [4 Theorem 3], which we refrain to present due to space restrictions. It produces a graph GG with O(n)O(n) nodes, maximum degree 4, and diameter O(Dlog⁡n)O(D\log n). It follows that CVP≤NCquasi\mathrm{CVP}\leq_{\mathrm{NC}}^{\mathrm{quasi}} 2-Degenerate, and the result follows thanks to Lemma 13.

Remarks on the Local Computation Time

The conditional lower bounds on the round complexity of 2-Degenerate in CONGEST derived in § 3.1.1 use Lemma 13 with local computation time O(nδ)O(n^\delta) for any δ<ε\delta<\varepsilon. Thus it allows the existence of an algorithm running in O(n1−ε)O(n^{1-\varepsilon}) rounds if it has Ω(nε)\Omega(n^\varepsilon) local computation time. Nevertheless, it is worth noticing that such local computation time is significantly larger than the one of a typical CONGEST algorithm. This subsection argues that an O(nδ)O(n^\delta) upper bound on the local computation may in fact be considered quite light, as far as the CONGEST model is concerned.

  • First, every node receives O(log⁡n)O(\log n) bits on each of its incident edges per round. Thus, in networks of constant degree, the total number of bits a node receives during rr rounds is O(rlog⁡n)O(r\log n). Roughly speaking, as a function of the input size, O(nδ)O(n^\delta) time corresponds to exponential time for r=polylog⁡(n)r=\operatorname{polylog}(n), and to sublinear time only for r=ω(nδ/log⁡n)r=\omega(n^\delta/\log n).

  • Second, in networks with constant degree, for most known algorithms, the local memory state of each node can be encoded in polylog⁡(n)\operatorname{polylog}(n) bits throughout their whole execution, and the computation performed at each node is often elementary (e.g., computing the minimum or maximum of O(log⁡n)O(\log n) integers, performing a constant number of XOR operations on O(log⁡n)O(\log n)-bit strings, etc.). This holds even for non-trivial problems such as leader election, maximal independent set, maximal matching, and minimum-weight spanning tree (see, e.g., [35, 36, 48]).

  • Last but not least, in our simulation lemma, the computation time T(n)T(n) used by each node per round may not only be measured assuming the sequential RAM model, but may assume the stronger parallel RAM (PRAM) model. That is, we allow each node to perform an amount of computation that takes T(n)T(n) time on a PRAM with poly⁡(n)\operatorname{poly}(n) processors. Even for T(n)=polylog⁡(n)T(n)=\operatorname{polylog}(n), each node can perform a significant amount of computation, such as prefix sums and matrix operations.

Lower Bound for other P-Complete Problems

Many P-complete problems π\pi satisfy CVP≤NCquasiπ\mathrm{CVP}\leq_{\mathrm{NC}}^{\mathrm{quasi}}\pi. The same lower bound as in Theorem 14 can be derived for these problems. This is for instance the case of (2−ε)(2-\varepsilon)-ApproxDegeneracy, and of other variants of kk-Core such as directed kk-cores, and kk-truss, which is the variant of kk-core in which each edge in the kk-truss must be part of k−2k-2 triangles. This follows from the known quasi-linear reductions from monotone circuit value to all of these problems [16 §3]. In fact, several reductions presented in [26] start from CVP, and are quasi-linear. Lemma 13 thus yields other results such as the following, with the same proof as for Theorem 14.

Theorem 15. Let ε∈(0,1)\varepsilon\in(0,1) and δ∈(0,ε)\delta\in(0,\varepsilon). Unless CVP admits a polynomial parallel speedup, none of the problems LexMIS, LexCol, and MaxFlow admit a CONGEST algorithm running in O(n1−ε)O(n^{1-\varepsilon}) rounds with O(nδ)O(n^\delta) local parallel computation time in nn-node networks of diameter O~(1)\widetilde{O}(1).

MaxFlow has a known unconditional lower bound of Ω~(D+n)\widetilde{\Omega}(D+\sqrt{n}) [18 §4]. Our lower bound is much higher, but is conditional. LexMIS and LexCol, which are classic problems in parallel complexity literature [26], had no previous lower bounds in CONGEST.

Remark. We note that our unconditional lower bound Ω~(n)\widetilde{\Omega}(\sqrt{n}) for Degeneracy (Corollary 7) can be extended to other problems, such as the circuit value problem or M2CVP. (Due to space restrictions, we do not explain these particular extensions.)

The remark above has consequences. Indeed, the circuit value is used as a base problem to prove the P-completeness of many other problems, so our lower bound can also be extended to the CONGEST version of many P-complete problems. Specifically, the unconditional lower bounds can be extended to a (P-complete) graph problem π\pi if there exists a reduction from M2CVP to π\pi which roughly preserves the graph structure, so that the “simulation argument” of Lemma 5 still works. This is the case for several variants of kk-core, using the reductions from [16], as well as for LexMIS and LexCol, using the standard reductions from [26]. This is because all these problems have the following property: in their reduction from M2CVP, each gate gg is mapped to a (constant-size) subgraph HgH_g, and if HgH_g has an edge to HfH_f in the final graph, then gg is connected to ff in the original circuit.

The Challenge of Finding Better Unconditional Lower Bounds

In this section, we discuss the ability to derive better (unconditional) lower bounds for the problems considered in this paper, above the apparent barrier of Ω~(n)\widetilde{\Omega}(\sqrt{n}). We show that recent tools for deriving lower bounds in CONGEST will not suffice.

On the Limitation of Moving Cuts

Das Sarma et al. [18] were the first to analyze the complexity of distributed algorithms on the graphs G(q,d,p)G(q,d,p), and derive lower bounds for CONGEST from lower bounds for communication complexity problems such as disjointness. In more recent literature [28], this technique has been dubbed “moving cuts” by Haeupler, Wajc, and Zuzic [29] who have generalized this technique, examining exactly which properties of the graph G(q,d,p)G(q,d,p) make disjointness hard to solve. Given any graph GG, the parameter MovingCut⁡(G)\operatorname{MovingCut}(G) is defined as the maximum distance β\beta for which there exists a set S={(si,ti),i∈{1,…,k}}S=\{(s_i,t_i),i\in\{1,\ldots,k\}\} of connectable source-sink pairs (i.e., vertex pairs that can be connected by vertex-disjoint paths in GG) and an edge-length assignment ℓ:E(G)→N≥1\ell:E(G)\to\mathbb{N}_{\ge1} satisfying:

∑e∈E(ℓ(e)−1)<k,and, for every i,j∈{1,…,k}, dist⁡ℓ(si,tj)≥β.\sum_{e\in E}(\ell(e)-1)<k,\quad\text{and, for every }i,j\in\{1,\ldots,k\},\ \operatorname{dist}_{\ell}(s_i,t_j)\ge\beta.

For the nn-vertex graph G=G(O(n),2,O(log⁡n))G=G(O(\sqrt{n}),2,O(\log n)), we have

MovingCut⁡(G)=Ω~(n) [29].\operatorname{MovingCut}(G)=\widetilde{\Omega}(\sqrt{n})\ \text{[29]}.

This lower bound is the source of the difficulty of computing Disj⁡β(s,r)\operatorname{Disj}^{\beta}(s,r) in GG (cf. Lemma 2). For several CONGEST problems, the framework in [29] enables one to derive the lower bound of Ω~(MovingCut⁡(G))\widetilde{\Omega}(\operatorname{MovingCut}(G)) rounds for every graph GG. Nevertheless, this lower bound does not hold for DEGENERACY. Indeed, the distributed peeling algorithm for 2-DEGENERATE takes O~(p)\widetilde{O}(p) rounds in the graph G(q,d,p)G(q,d,p)12, which has diameter 2p+22p+2. As a consequence, Ω~(MovingCut⁡(G))\widetilde{\Omega}(\operatorname{MovingCut}(G)) is not a lower bound for the complexity of DEGENERACY in CONGEST.

Remark. Haeupler, Wajc, and Zuzic [29] also designed algorithms for several problems running in O~(MovingCut⁡(G))\widetilde{O}(\operatorname{MovingCut}(G)). One might wonder whether such an algorithm exists for DEGENERACY. Although our unconditional lower bound does not show otherwise, Section 4 provides strong evidence that such an algorithm is unlikely to exist.

On the Limitation of Small Cuts

Here we prove that the framework by Abboud et al. [1], which is used to obtain many polynomial lower bounds in CONGEST, cannot be directly used to obtain any non-trivial lower bound for DEGENERACY. We start with a review of the framework from [1].

The Framework

The Framework. A two-party communication problem [49] is specified by a function f:A×B→{0,1}f:A\times B\to\{0,1\}. It involves two players, referred to as Alice and Bob. Alice receives an input a∈Aa\in A and Bob receives input b∈Bb\in B. The goal of the players is to output f(a,b)f(a,b). The communication complexity of ff is the number of bits the two players must exchange in the worst instance. It is denoted by CC⁡(f)\operatorname{CC}(f), or CC⁡R(f)\operatorname{CC}^{\mathrm{R}}(f) if randomization is allowed. The following definition is borrowed from [1].

Definition 16. Let f:A×B→{0,1}f:A\times B\to\{0,1\} be a function, and let PP be a graph predicate. A family of graphs {Gx,y=(V,Ex,y):(x,y)∈A×B}\{G_{x,y}=(V,E_{x,y}):(x,y)\in A\times B\} with a partition V=VA∪VBV=V_A\cup V_B, and possibly labels on the vertices and edges, is said to be a family of lower bound graphs w.r.t. ff and PP if the following properties hold:

  1. only the edges in G[VA]G[V_A] and their labels may depend on xx;

  2. only the edges in G[VB]G[V_B] and their labels may depend on yy;

  3. f(x,y)f(x,y) is uniquely determined by whether Gx,yG_{x,y} satisfies the predicate PP.

Abboud et al. [1] proved the following theorem, and derived (unconditional) lower bounds in CONGEST from it, for several problems such as exact diameter and vertex cover.

Theorem 17 (Theorem 6 in [1]). Let f:{0,1}K×{0,1}K→{0,1}f:\{0,1\}^{K}\times\{0,1\}^{K}\to\{0,1\} be a function, and let PP be a graph predicate. If there exists a family {Gx,y=(V,Ex,y):(x,y)∈{0,1}K×{0,1}K}\{G_{x,y}=(V,E_{x,y}):(x,y)\in\{0,1\}^{K}\times\{0,1\}^{K}\} of lower bound graphs w.r.t. ff and PP with V=VA∪VBV=V_A\cup V_B and C=E[VA,VB]C=E[V_A,V_B], then every distributed algorithm for deciding PP requires Ω(CC⁡(f)/∣C∣⋅log⁡∣V∣)\Omega(\operatorname{CC}(f)/|C|\cdot\log|V|) rounds in the CONGEST model, and every randomized algorithm requires Ω(CC⁡R(f)/∣C∣⋅log⁡∣V∣)\Omega(\operatorname{CC}^{\mathrm{R}}(f)/|C|\cdot\log|V|) rounds.

Why the Framework of Small Cuts Fails for Degeneracy

Let f:A×B→{0,1}f:A\times B\to\{0,1\} be a function. If it is possible to use an algorithm for kk-DEGENERATE to decide, given any (x,y)∈A×B(x,y)\in A\times B, whether f(x,y)=1f(x,y)=1, that is, if there exists a family of lower bound graphs w.r.t. ff and kk-DEGENERATE, then we will show an efficient communication protocol for ff. This implies that the communication complexity CC⁡(f)\operatorname{CC}(f) is low and, hence, Theorem 17 yields only trivial lower bounds for kk-DEGENERATE. Recall that, in the peeling algorithm, the vertices with degree at most kk are progressively removed from the input graph GG, until no vertices have degree at most kk. In the end, the remaining graph is precisely the (k+1)(k+1)-core of GG, and GG is kk-degenerate if and only if the (k+1)(k+1)-core is empty. The order in which the vertices are peeled (which may not be unique) is called a peeling order for the (k+1)(k+1)-core. With this in mind, we can show the communication protocol.

Theorem 18. Let k≥2k \ge2 be an integer, and let f:A×B→{0,1}f : A \times B \to\{0,1\} be a function. If there exists a family of lower bound graphs {Gx,y=(V,Ex,y):(x,y)∈A×B}\{G_{x,y} = (V, E_{x,y}) : (x,y) \in A \times B\} w.r.t. ff and kk-Degenerate where V=VA∪VBV = V_A \cup V_B and C=E[VA,VB]C = E[V_A,V_B], then CC⁡(f)=O(∣C∣⋅log⁡∣V∣)\operatorname{CC}(f) = O(|C| \cdot\log|V|).

Proof. Let us assume that there exists a family of lower bound graphs {Gx,y=(V,Ex,y):(x,y)∈A×B}\{G_{x,y} = (V, E_{x,y}) : (x,y) \in A \times B\} as in the statement of the theorem. We first prove that there is a communication protocol to compute f(x,y)f(x,y) using O(∣C∣⋅log⁡∣V∣)O(|C| \cdot\log|V|) bits of communication for k=2k = 2, and we show later how to generalize this fact to larger kk. For any (x,y)∈A×B(x,y) \in A \times B, let us consider Gx,yG_{x,y}. Let CA=V(C)∩VAC_A = V(C) \cap V_A and CB=V(C)∩VBC_B = V(C) \cap V_B. Moreover, let G~A\widetilde{G}_A be the graph G[VA]G[V_A] and, for every ab∈Cab \in C such that a∈CAa \in C_A and b∈CBb \in C_B, add a copy LabL_{ab} of the graph in Figure 5(a) to G~A\widetilde{G}_A, connecting a∈CAa \in C_A to u∈V(Lab)u \in V(L_{ab}). Define G~B\widetilde{G}_B similarly. See Figure 6 for an example. We now describe a communication protocol between Alice and Bob to determine whether GG is 2-degenerate, and thus to compute f(x,y)f(x,y), by simulating the peeling algorithm. This protocol is described as Algorithm 1.

Gadgets used in Theorem 18 for 2-Degenerate and 3-Degenerate

Figure 5. (a) Gadget used in Theorem 18 for 2-Degenerate. In any peeling order for the 3-core, vertex aa is always the first to be removed (if it is removed), independently from the rest of the graph. Furthermore, if aa is removed, then the rest of the gadget will be removed as well. (b) Similar gadget for 3-Degenerate.

Example of how Alice builds graph $\widetilde{G}_A$ from the original graph $G$ and her set of vertices

Figure 6. Example of how Alice builds graph G~A\widetilde{G}_A from the original graph GG and her set of vertices.

Protocol 1: Communication protocol for computing f(x,y)f(x,y).

  1. Alice and Bob build graphs G~A\widetilde{G}_A and G~B\widetilde{G}_B, respectively.

  2. repeat

  3. Alice peels vertices of degree at most 2 from G~A\widetilde{G}_A until none exists.

  4. Alice sends to Bob the list of identifier pairs (a,b)(a,b) for each gadget LabL_{ab} she peeled.

  5. For each pair (a,b)(a,b) that Bob received, he removes the gadget LbaL_{ba} from G~B\widetilde{G}_B.

  6. Bob peels vertices of degree at most 2 from G~B\widetilde{G}_B until none exists.

  7. Bob sends to Alice the list of identifier pairs (b,a)(b,a) for each gadget LbaL_{ba} he peeled.

  8. if Alice received a non-empty list then

  9. For each pair (b,a)(b,a) that Alice received, she removes the gadget LabL_{ab} from G~A\widetilde{G}_A.

  10. until Alice receives an empty list

  11. Both players determine f(x,y)f(x,y) based on whether their remaining graphs are empty.

Total communication. Each player sends O(log⁡∣V∣)O(\log|V|) bits per gadget peeled, and each gadget is peeled at most once, since edges can only be removed. Additionally, apart from the very first message, whenever an empty list is sent, the protocol sends at most one more empty list before terminating, using O(1)O(1) bits. Thus, the total number of bits exchanged between the two players is O(∣C∣⋅log⁡∣V∣)O(|C| \cdot\log|V|).

Correctness. Let KAK_A and KBK_B be the remaining graphs for Alice and Bob, respectively, that is, their computed 3-cores. First note that LabL_{ab} is in KAK_A if and only if LbaL_{ba} is in KBK_B. This is because when one is peeled by lines 3 or 6, the other is removed in lines 5 or 9, respectively. Consider the graph KK formed by merging KAK_A and KBK_B and replacing gadget pairs LabL_{ab} and LbaL_{ba} by the edge abab. We will show that KK is precisely KGK_G, the 3-core of GG.

Note that the degree of all vertices from VAV_A and VBV_B is the same in KK as in KAK_A and KBK_B, respectively, since each gadget LabL_{ab} contributes one to the degree of aa, and it was replaced by the edge abab. So KK has minimum degree at least 3 and thus K⊆KGK \subseteq K_G. For the purpose of contradiction, let us suppose that KG⊈KK_G \not\subseteq K, and let vv be the first vertex in KGK_G peeled by Alice or Bob. Let G~A\widetilde{G}_A and G~B\widetilde{G}_B be the graphs G~A\widetilde{G}_A and G~B\widetilde{G}_B at the time tt when vv was chosen to be peeled. Suppose, w.l.o.g., that v∈V(G~A)v \in V(\widetilde{G}_A), and let us show that dG~A(v)≥dKG(v)d_{\widetilde{G}_A}(v) \ge d_{K_G}(v). For any edge vw∈E(KG)vw \in E(K_G), since vv was the first vertex in KGK_G to be peeled, we know ww remains in the graph, that is, w∈V(G~A)∪V(G~B)w \in V(\widetilde{G}_A) \cup V(\widetilde{G}_B). If w∈V(G~A)w \in V(\widetilde{G}_A), then vw∈E(G~A)vw \in E(\widetilde{G}_A). If w∈V(G~B)w \in V(\widetilde{G}_B), then let us show that Lvw⊆G~AL_{vw} \subseteq\widetilde{G}_A. First, LvwL_{vw} was not peeled in line 3, since such peeling would have started by vv; second, LvwL_{vw} was not removed in line 9, since that would imply that ww is peeled by Bob in order to peel LwvL_{wv} in line 6. Thus, at least 3 edges are incident to vv in G~A\widetilde{G}_A, a contradiction. We conclude that KG⊆KK_G \subseteq K. This shows that the 3-core is computed correctly by Alice and Bob, and thus whether GG is 2-degenerate. Since {Gx,y}\{G_{x,y}\} is a family of lower bound graphs w.r.t. ff and 2-Degenerate, this implies that f(x,y)f(x,y) is computed correctly.

To generalize this result to k>2k > 2, it suffices to change the graph from Figure 5(a) to any graph with no (k+1)(k+1)-core but such that all vertices have degree at least k+1k+1, except for vv which has degree exactly kk. See Figure 5(b). □\square

It follows from Theorem 17 that, for any k≥2k \ge2, using the framework in [1], one can only obtain trivial lower bounds of Ω(CC⁡(f)/(∣C∣⋅log⁡∣V∣))=Ω(1)\Omega(\operatorname{CC}(f)/(|C| \cdot\log|V|)) = \Omega(1) rounds for kk-DEGENERATE.

Remark. It is possible to extend the framework from [1] to obtain polynomial lower bounds for DEGENERACY. For that, we however need to switch to the pointer chasing problem, which has more complex lower bounds that depend on the number of alternations between the two players during the communication protocol, and which requires to modify Theorem 17 accordingly. We can do the appropriate modifications, but this only yields a lower bound Ω~(n3)\widetilde{\Omega}(\sqrt[3]{n}) for DEGENERACY, which is weaker than the one obtained in Section 3. The techniques and ideas used in the proof are however interesting, and they may be adapted to get better lower bounds for other problems. The details are given next.

Extension of the Small Cuts Techniques

We established above that the framework by Abboud et al. [1] cannot be directly used to obtain polynomial lower bounds for DEGENERACY. In this section, we extend the framework, consider the pointer chasing problem, combined with the bit gadget technique from [6], in order to obtain Ω~(n3)\widetilde{\Omega}(\sqrt[3]{n}) lower bounds. For simplicity, we provide lower bounds for the problem kk-CORE, in which each node outputs whether it is in the kk-core of the network.

Extending the Framework

We start by formalizing the definitions of communication complexity from Section 5.2, in order to introduce round restrictions. A communication protocol π\pi for function ff is a procedure in which Alice and Bob exchange messages, where each message may depend on their input, the messages received so far, and possibly on some (public) random bits, in the randomized case. At the end, both players output f(a,b)f(a,b).

A protocol π\pi is said to run in rr rounds if the players exchange messages in rr alternating turns, with Alice starting. The deterministic communication complexity of ff over rr rounds, denoted CCr(f)\mathrm{CC}_r(f), is the minimum of CC(π)\mathrm{CC}(\pi) over all deterministic protocols π\pi for ff that run in rr rounds, and we define CCrR(f)\mathrm{CC}^{R}_r(f) similarly for the randomized case.

Definition 19 (Pointer Chasing). The (ℓ,m)(\ell,m) history pointer chasing problem, or HistPCℓm\mathrm{HistPC}^{m}_{\ell}, is a two-party communication complexity problem. There are two functions fA,fB:[m]→[m]f_A,f_B:[m]\to[m] known by Alice and Bob, respectively. The goal is, for all i∈[ℓ]i\in[\ell], to compute oi=fi(fi−1(⋯f1(1)⋯ ))o_i=f_i(f_{i-1}(\cdots f_1(1)\cdots)), where fif_i is fAf_A if ii is odd, and fBf_B otherwise.

It is easy to solve HistPCℓm\mathrm{HistPC}^{m}_{\ell} by exchanging Θ(ℓ⋅log⁡m)\Theta(\ell\cdot\log m) bits over ℓ\ell rounds. Alice starts by sending fA(1)f_A(1) to Bob, who then sends fB(fA(1))f_B(f_A(1)) to Alice and so on. However, solving this problem with fewer rounds substantially increases the amount of bits that need to be exchanged, as formalized below.

Proposition 20 (Theorem 6.1 in [41]). For ℓ=O(m)\ell=O(\sqrt{m}), CCℓ/1000R(HistPCℓm)=Ω(m)\mathrm{CC}^{R}_{\ell/1000}(\mathrm{HistPC}^{m}_{\ell})=\Omega(m).

The deterministic case, which works even for ℓ−1\ell-1 rounds, was established in [46]. Mittal [41] noted that it was possible to obtain the same asymptotic bound for the randomized case when restricted to ℓ/1000\ell/1000 rounds instead.13

Since, by Theorem 18, we know it is not possible to use Theorem 17 for a non-trivial lower bound for kk-Core, we present a stronger version of the theorem, which considers lower bounds that include round restrictions, and which allows a graph function FF, instead of simply a predicate PP.

A graph function FF is a function mapping each graph to a string of bits. In the CONGEST problem of computing a graph function FF on network GG, each node has to output F(G)F(G) at the end of the algorithm. Note that a graph predicate is simply a graph function that outputs a single bit. We now slightly modify Definition 16 to allow graph functions.

Definition 21. Let f:A×B→{0,1}f:A\times B\to\{0,1\} be a function, and let FF be a graph function. A family of graphs {Gx,y=(V,Ex,y):(x,y)∈A×B}\{G_{x,y}=(V,E_{x,y}):(x,y)\in A\times B\} with a partition V=VA∪VBV=V_A\cup V_B, and possibly labels on the vertices and edges, is said to be a family of lower bound graphs w.r.t. ff and FF if the following properties hold:

  1. only edges and labels in G[VA]G[V_A] may depend on xx;

  2. only edges and labels in G[VB]G[V_B] may depend on yy;

  3. f(x,y)f(x,y) is uniquely determined by F(Gx,y)F(G_{x,y}).

Theorem 22. Fix an integer r≥1r\geq1, a function f:A×B→{0,1}f:A\times B\to\{0,1\}, and a graph function FF. If there exists a family {Gx,y=(V,Ex,y)}\{G_{x,y}=(V,E_{x,y})\} of lower bound graphs w.r.t. ff and FF, with V=VA∪VBV=V_A\cup V_B and C=E[VA,VB]C=E[V_A,V_B], then every deterministic algorithm for computing FF in the CONGEST model requires Ω(min⁡{r,CCr−1(f)/∣C∣⋅log⁡∣V∣})\Omega(\min\{r,\mathrm{CC}_{r-1}(f)/|C|\cdot\log|V|\}) rounds, and every randomized algorithm requires Ω(min⁡{r,CCr−1R(f)/∣C∣⋅log⁡∣V∣})\Omega(\min\{r,\mathrm{CC}^{R}_{r-1}(f)/|C|\cdot\log|V|\}) rounds.

Proof. Let R(n)R(n) be the round complexity of a CONGEST algorithm for graph function FF in nn-node networks. Using the same simulation as for establishing Theorem 17, we obtain a communication protocol π\pi for ff. This protocol runs in O(R(n))O(R(n)) rounds by simulating each CONGEST round with two alternating communication rounds. Moreover, it exchanges O(R(n)⋅∣C∣⋅log⁡n)O(R(n)\cdot|C|\cdot\log n) total bits as the players can only communicate O(log⁡n)O(\log n) bits per round per edge in the cut.

If π\pi is deterministic, then either it takes at least rr rounds, or it exchanges Ω(CCr−1(f))\Omega(\mathrm{CC}_{r-1}(f)) bits. In the former case, we have R(n)=Ω(r)R(n)=\Omega(r). In the latter, R(n)⋅∣C∣⋅log⁡n=Ω(CCr−1(f))R(n)\cdot|C|\cdot\log n=\Omega(\mathrm{CC}_{r-1}(f)). By combining both cases, we obtain R(n)=Ω(min⁡{r,CCr−1(f)/∣C∣⋅log⁡∣V∣})R(n)=\Omega(\min\{r,\mathrm{CC}_{r-1}(f)/|C|\cdot\log|V|\}). The case of a randomized π\pi follows from the same arguments. □\square

Using the Extended Framework

We will start by deriving lower bounds for M2CVP, and later adapting them for kk-CORE. We consider the variant of M2CVP in CONGEST in which each vertex must compute the value of the corresponding gate in the circuit. The following proposition is the main technical reduction of this section.

Proposition 23. For any integers ℓ,m≥2\ell,m \ge2, there exists a family of lower bound graphs {Gx,y=(V,Ex,y)}\{G_{x,y}=(V,E_{x,y})\} w.r.t. HistPCℓm_\ell^m and M2CVP, with V=VA∪VBV=V_A\cup V_B and C=E[VA,VB]C=E[V_A,V_B], such that ∣C∣=Θ(ℓ⋅log⁡m)|C|=\Theta(\ell\cdot\log m), ∣V∣=Θ(ℓ⋅m⋅log⁡(ℓ⋅m))|V|=\Theta(\ell\cdot m\cdot\log(\ell\cdot m)), with the graphs having diameter O(log⁡∣V∣)O(\log|V|).

This proposition means that, from a pointer chasing instance, we can obtain a graph which encodes a circuit such that, for each i∈[ℓ]i\in[\ell], we can determine oio_i based on the values of each of the gates. We first use the proposition to derive the lower bounds and then present its proof.

Corollary 24. For any integers ℓ,m≥2\ell,m\ge2, and k≥3k\ge3, there exists a family of lower bound graphs {Gx,y=(V,Ex,y)}\{G_{x,y}=(V,E_{x,y})\} w.r.t. HistPCℓm_\ell^m and kk-CORE, with V=VA∪VBV=V_A\cup V_B and C=E[VA,VB]C=E[V_A,V_B], such that ∣C∣=Θ(ℓ⋅log⁡m)|C|=\Theta(\ell\cdot\log m), ∣V∣=Θ(ℓ⋅m⋅log⁡(ℓ⋅m))|V|=\Theta(\ell\cdot m\cdot\log(\ell\cdot m)), with the graphs having diameter O(log⁡∣V∣)O(\log|V|).

Proof. For any input (x,y)(x,y) for HistPCℓm_\ell^m, let Gx,yG_{x,y} be the graph given by Proposition 23. Then use the standard reduction from M2CVP to kk-CORE (see [4 §3]) to obtain Gx,y′G'_{x,y}. This reduction preserves the order of the number of vertices and cut sizes, and it is possible to recover the value of all gates of Gx,yG_{x,y} from the kk-core of Gx,y′G'_{x,y}. Therefore, {Gx,y′}\{G'_{x,y}\} is a family that satisfies the statement. □\square

Theorem 25. M2CVP on nn-node O(log⁡n)O(\log n)-diameter networks requires Ω(n/log⁡3n3)\Omega(\sqrt[3]{n/\log^3 n}) rounds for any randomized algorithm in the CONGEST model.

Proof. Suppose M2CVP can be solved in the CONGEST model in R(n)R(n) rounds. Consider an instance of HistPCℓm_\ell^m for some ℓ=O(m)\ell=O(\sqrt{m}) that we will specify later. By Proposition 23, there exists some graph G=(V,E)G=(V,E) with cut C=E[VA,VB]C=E[V_A,V_B], which encodes an instance of M2CVP, such that, for each i∈[ℓ]i\in[\ell], the value of oio_i can be recovered from the values of the gates of the circuit, with ∣C∣=Θ(ℓ⋅log⁡m)|C|=\Theta(\ell\cdot\log m) and n=∣V∣=Θ(ℓ⋅m⋅log⁡(ℓ⋅m))=Θ(ℓ⋅m⋅log⁡m)n=|V|=\Theta(\ell\cdot m\cdot\log(\ell\cdot m))=\Theta(\ell\cdot m\cdot\log m).

Using Theorem 22 with r=ℓ/1000+1r=\ell/1000+1, and Proposition 20, we get that

R(∣V∣)=Ω(min⁡{ℓ1000+1,CC⁡ℓ/1000R(HistPC⁡ℓm)ℓ⋅log⁡m⋅log⁡∣V∣})=Ω(min⁡{ℓ,mℓ⋅log⁡2m}).R(|V|)=\Omega\left(\min\left\{\frac{\ell}{1000}+1,\frac{\operatorname{CC}_{\ell/1000}^{R}(\operatorname{HistPC}_{\ell}^{m})}{\ell\cdot\log m\cdot\log|V|}\right\}\right)=\Omega\left(\min\left\{\ell,\frac{m}{\ell\cdot\log^2m}\right\}\right).

because ℓ=O(m)\ell=O(\sqrt{m}). This is maximized when ℓ=m/(ℓ⋅log⁡2m)\ell=m/(\ell\cdot\log^2m) and therefore ℓ=m/log⁡m=O(m)\ell=\sqrt{m}/\log m=O(\sqrt{m}), which implies that ∣V∣=Θ(m3)|V|=\Theta(\sqrt{m^3}) and R(∣V∣)=Ω(m/log⁡m)R(|V|)=\Omega(\sqrt{m}/\log m). Changing variables, we obtain

R(n)=Ω(n3/log⁡n)=Ω(n/log⁡3n3),R(n)=\Omega(\sqrt[3]{n}/\log n)=\Omega\left(\sqrt[3]{n/\log^3n}\right),

using the fact that R(O(x))=O(R(x))R(O(x))=O(R(x)) when R=poly⁡(x)R=\operatorname{poly}(x).

Theorem 26. For any k≥3k\ge3, kk-CORE on nn-node O(log⁡n)O(\log n)-diameter networks requires Ω(n/log⁡3n3)\Omega(\sqrt[3]{n/\log^3n}) rounds for any randomized algorithm in the CONGEST model.

Proof. Identical to Theorem 25, but using Corollary 24 instead of Proposition 23.

Note that the requirement that k≥3k\ge3 in the previous result is tight, in a sense, since 2-CORE can be solved in O(log⁡n)O(\log n) rounds on O(log⁡n)O(\log n)-diameter networks, as we show in § 3.4.

Remark. Theorem 26 also holds for any (2−ε)(2-\varepsilon)-approximation of the core value of each vertex. It also holds for the directed kk-core variant, and the kk-truss problem. This is due to the known reductions from M2CVP to all of these problems [16 §3], and the fact that these reductions preserve the order of the cut sizes. In general, Theorem 26 holds for many P-complete graph problems, and this technique for establishing hardness may be reused. This can be done for any problem π\pi for which a reduction from M2CVP exists where the size of the Alice-Bob cut in Proposition 23 is roughly maintained, and that the values of all gates can be recovered. For example, it also follows for LexMIS and LexCol.

With the motivation in place, we now prove this section’s main technical result.

Proof (Proof of Proposition 23). We will describe a family of lower bound graphs w.r.t. HistPCmℓ\mathrm{HistPC}_{m}^{\ell} and M2CVP. At first, we consider circuits with unbounded diameter, fan-in, and fan-out. Consider an instance of HistPCmℓ\mathrm{HistPC}_{m}^{\ell}. That is, we have functions fA,fB:[m]→[m]f_A, f_B : [m] \to[m]. The input is given to two players, Alice and Bob, so that Alice knows fAf_A, and Bob knows fBf_B. To simplify notation, we take fif_i to be fAf_A if ii is odd, and fBf_B if ii is even. We will build a monotone circuit that can be used to compute oi=fi(⋯f1(1)⋯ )o_i = f_i(\cdots f_1(1)\cdots) for each i∈[ℓ]i \in[\ell].

Construction of the circuit. The circuit will have ℓ\ell layers, where the iith layer corresponds to function fif_i. Follow the description looking at the example in Figure 7. Layer ii has AND-gates Xi={xi1,…,xim}X_i = \{x_{i1}, \ldots, x_{im}\} and OR-gates Yi={yi1,…,yim}Y_i = \{y_{i1}, \ldots, y_{im}\}, as well as OR-gates

Example of the circuit created for $\ell=2$ and $m=5$

Figure 7. Example of the circuit created when ℓ=2\ell= 2, m=5m = 5, fA(i)=Aif_A(i) = A_i and fB(i)=Bif_B(i) = B_i, with A=[3,2,3,1,4]A = [3, 2, 3, 1, 4] and B=[3,2,5,2,4]B = [3, 2, 5, 2, 4]. Gates and wires with value 1 are bold. In particular, the output gate (marked with a ⋆\star) has value 1 because fB(fA(1))=5f_B(f_A(1)) = 5.

Fi↓={fi1↓,…,fi⌈log⁡m⌉↓} and Fi↑={fi1↑,…,fi⌈log⁡m⌉↑},F_i^{\downarrow} = \{f_{i1}^{\downarrow}, \ldots, f_{i\lceil\log m\rceil}^{\downarrow}\} \text{ and } F_i^{\uparrow} = \{f_{i1}^{\uparrow}, \ldots, f_{i\lceil\log m\rceil}^{\uparrow}\},

and

Ti↓={ti1↓,…,ti⌈log⁡m⌉↓} and Ti↑={ti1↑,…,ti⌈log⁡m⌉↑}.T_i^{\downarrow} = \{t_{i1}^{\downarrow}, \ldots, t_{i\lceil\log m\rceil}^{\downarrow}\} \text{ and } T_i^{\uparrow} = \{t_{i1}^{\uparrow}, \ldots, t_{i\lceil\log m\rceil}^{\uparrow}\}.

Let Li=Xi∪Yi∪Fi↓∪Fi↑∪Ti↓∪Ti↑L_i = X_i \cup Y_i \cup F_i^{\downarrow} \cup F_i^{\uparrow} \cup T_i^{\downarrow} \cup T_i^{\uparrow} be the set of gates in layer ii. Now, let jkj^k be the kk-th (least significant) bit of jj in its binary representation, and let

Bi↓(j)={tik↓:jk=1}∪{fik↓:jk=0}.B_i^{\downarrow}(j) = \{t_{ik}^{\downarrow} : j^k = 1\} \cup\{f_{ik}^{\downarrow} : j^k = 0\}.

Define Bi↑(j)B_i^{\uparrow}(j) similarly, but using tik↑t_{ik}^{\uparrow} and fik↑f_{ik}^{\uparrow}. The wires between gates in layer ii are as follows, for each j∈[m]j \in[m]:

  • from all gates in Bi↓(j)B_i^{\downarrow}(j) to xijx_{ij},

  • from xijx_{ij} to yifi(j)y_{i f_i(j)},

  • from yijy_{ij} to all gates in Bi↑(j)B_i^{\uparrow}(j).

Additionally, for each i∈[ℓ−1]i \in[\ell- 1] and k∈[⌈log⁡m⌉]k \in[\lceil\log m\rceil], we have wires from fik↑f^{\uparrow}_{ik} to f(i+1)k↑f^{\uparrow}_{(i+1)k} and from tik↓t^{\downarrow}_{ik} to t(i+1)k↓t^{\downarrow}_{(i+1)k}. Finally, add a 1-gate ss connected to B1↑(1)B^{\uparrow}_{1}(1). The output of the circuit is tℓ1↑t^{\uparrow}_{\ell1}. Alice will own

VA={s}∪⋃i oddLi,V_A = \{s\} \cup\bigcup_{i\ \mathrm{odd}} L_i,

while Bob will own

VB=⋃i evenLi.V_B = \bigcup_{i\ \mathrm{even}} L_i.

Note the wires in E[VA]E[V_A] depend only on the functions with odd indices (i.e., known by Alice), and the wires in E[VB]E[V_B] depend only on the functions with even indices (i.e., known by Bob). The wires in E[VA,VB]E[V_A,V_B] are exactly those connecting Fi↑,Ti↑F_i^{\uparrow}, T_i^{\uparrow} to Fi+1↓,Ti+1↓F_{i+1}^{\downarrow}, T_{i+1}^{\downarrow}, and do not depend on any function. Furthermore, the size of the cut E[VA,VB]E[V_A,V_B] is O(ℓ⋅log⁡m)O(\ell\cdot\log m). One can think of getting rid of Fi↑F_i^{\uparrow} and Ti↑T_i^{\uparrow}, connecting yijy_{ij} directly to Fi+1↓F_{i+1}^{\downarrow}, Ti+1↓T_{i+1}^{\downarrow}, or Xi+1X_{i+1}, but this would increase the size of the E[VA,VB]E[V_A,V_B] cut to Ω(m⋅ℓ)\Omega(m \cdot\ell).

In order to bound the diameter of the circuit (when considered as an undirected graph), each player adds a 1-gate connected to all their AND-gates, and a 0-gate connected to all their OR-gates. Note this does not affect the value of the circuit, or the size of the cut, and it makes the diameter O(1)O(1). To bound the fan-in and fan-out to 2, use the usual construction of replacing high-fan-in gates by balanced binary trees of gates of the same type, and high-fan-out gates by balanced binary trees of OR-gates. This increases the diameter by a logarithmic factor. The final circuit has O(ℓ⋅m⋅log⁡(ℓ⋅m))O(\ell\cdot m \cdot\log(\ell\cdot m)) gates and wires, and diameter O(log⁡(ℓ⋅m))O(\log(\ell\cdot m)).

Correctness. We can show by induction on ii that

  1. xijx_{ij} evaluates to 1 if and only if fi−1(fi−2(⋯f1(1)⋯ ))=jf_{i-1}(f_{i-2}(\cdots f_1(1)\cdots)) = j,

  2. yijy_{ij} evaluates to 1 if and only if fi(fi−1(⋯f1(1)⋯ ))=jf_i(f_{i-1}(\cdots f_1(1)\cdots)) = j,

  3. gates in Fi↓F_i^{\downarrow} and Ti↓T_i^{\downarrow} evaluate to 1 if and only if they are in Bi↓(fi−1(⋯f1(1)⋯ ))B_i^{\downarrow}(f_{i-1}(\cdots f_1(1)\cdots)), and

  4. gates in Fi↑F_i^{\uparrow} and Ti↑T_i^{\uparrow} evaluate to 1 if and only if they are in Bi↑(fi(fi−1(⋯f1(1)⋯ ))B_i^{\uparrow}(f_i(f_{i-1}(\cdots f_1(1)\cdots))).

When i=0i = 0, (3) follows from our construction, because we added ss connected to B1↑(1)B_1^{\uparrow}(1) and no other gates in layer 1 have inputs. For i>0i > 0, (3) holds because of (2) for layer i−1i-1, and the fact that fik↑f^{\uparrow}_{ik} and tik↓t^{\downarrow}_{ik} receive inputs only from f(i−1)k↑f^{\uparrow}_{(i-1)k} and t(i−1)k↓t^{\downarrow}_{(i-1)k}, respectively. Now, (1) holds because of (3), and the fact that xijx_{ij} is connected to Bi↓(j)B_i^{\downarrow}(j) and any k≠jk \ne j is connected to some gate in Bi↓(k)B_i^{\downarrow}(k) that evaluates to 0. Moreover, (2) holds because of (1) and the fact that yijy_{ij} is connected to all xikx_{ik} such that fi(k)=jf_i(k) = j. Finally, (4) holds because of (2) and the connections from yijy_{ij} to Bi↑(j)B_i^{\uparrow}(j).

Thus, we can correctly determine oi=jo_i = j where yijy_{ij} is the only gate on that column with value 1. Hence, we have a family of lower bound graphs w.r.t. HistPCℓ\ell and M2CVP, where each graph is the undirected version of the circuit, and each vertex has information (labels) about which type of gate it is and the orientation of the edges incident on it. □

An Efficient Algorithm for Computing the 2-Core

In this section, we present algorithms for degeneracy in CONGEST. Note that from an algorithm for kk-CORE we can easily create one for (k−1)(k - 1)-DEGENERATE.14 Therefore, for the remainder of the section, we focus on algorithms for the kk-core problem.

For k≥3k \ge3, the straightforward O(n)O(n)-round algorithm matches the lower bound of Theorem 14 up to subpolynomial factors. However, for k=2k = 2, we provide a more efficient algorithm that runs in O(D)O(D) rounds on graphs of diameter DD, thus matching the known Ω(D)\Omega(D) lower bound, which holds even for the LOCAL model (see [14 §1]).

We start by describing a distributed CONGEST algorithm proposed in [14] for computing the core values of a given graph GG. During the execution, each node uu of GG maintains a local estimate of its core value, which is initialized to its degree. Throughout the execution, its estimate is at least its true core value. At each round, each node uu broadcasts its core value estimate to its neighbors. Once uu receives all current estimates from its neighbors, it updates its estimate to the largest xx such that uu has at least xx neighbors with estimate at least xx. For an nn-node graph, after nn rounds, the estimates are the true core values [14 §I.A], so all nodes terminate.

Remark. Even on nn-node graphs with constant diameter, the number of rounds needed for the algorithm to stabilize (i.e., every node has its true core value) might be Θ(n)\Theta(n). Indeed, for the graph consisting of an (n−1)(n-1)-node path plus a universal node, the algorithm takes ⌈n−22⌉\left\lceil\frac{n-2}{2}\right\rceil rounds to stabilize. In fact, at the end of round i∈{1,2,…,⌊n−42⌋}i \in\{1,2,\ldots,\left\lfloor\frac{n-4}{2}\right\rfloor\}, every node at distance at most ii from the endpoints of the (n−1)(n-1)-node path has set its core value estimate to 2, while all other nodes, including the universal node, have their estimate equal to 3. Finally, in round ⌈n−22⌉\left\lceil\frac{n-2}{2}\right\rceil, every node sets its core value estimate to its true core value, which is 2.

We now present a more efficient CONGEST algorithm when k=2k=2.

Theorem 27. 2-Core can be solved in O(D)O(D) rounds in the CONGEST model on nn-node networks of diameter DD.

Proof. Let GG be a graph of diameter DD. The first phase of our algorithm starts with the execution of the standard procedure for selecting as leader a node ss of GG and computing a breadth-first search tree TT of GG rooted at ss. This takes O(D)O(D) rounds in the CONGEST model (see [30 §5.5-5.6] for details). The execution of this procedure determines, for each node vv of GG, its distance to the root ss, a pointer p[vv] to its parent, and the collection of identifiers of vv’s children in TT. In the next phases, each node vv uses two additional Boolean variables, up[vv] and down[vv], to identify vv as unmarked, marked up, marked down, or marked both up and down. Initially, these two variables are set to false at each node.

At the start of the second (upcast) phase of our algorithm, each node vv incident to a non-tree edge sets variable up[vv] to true conveying that it belongs to a cycle in GG. Afterward, every leaf vv of TT upcasts up[vv] to its parent. When an internal node uu of TT has seen all messages being upcast by its children, it sets up[uu] to true if it received at least one true value. The second phase finishes when the root of TT has processed all its children’s messages. Besides this, in preparation for the third phase, during the upcast phase, vv sets down[vv] to true if it received at least two true values from its children.

During the third (downcast) phase, messages are propagated downward through TT starting from the root ss, which broadcasts down[ss]. When a node vv receives the message from its parent, it sets down[vv] to true if the message is true, and then it propagates down[vv] to its children. See Figure 8 for an example.

The final state of the 2-core algorithm on an example graph

Figure 8. The final state of the 2-core algorithm on an example graph. The solid black edges form a BFS tree rooted at node A. The dashed red edges are non-tree edges. The small arrows next to a node vv indicate its final state: a blue upward arrow for up⁡[v]\operatorname{up}[v] and a purple downward arrow for down⁡[v]\operatorname{down}[v]. A node is in the 2-core, colored blue in the image, if and only if it has both marks at the end of the algorithm.

Finally, a node vv claims that it belongs to the 2-core of GG if and only if both up[vv] and down[vv] equal true at the end of the downcast phase.

By construction, our algorithm completes in O(D)O(D) rounds in CONGEST, since building the breadth-first search tree and both the upcast and downcast phases take O(D)O(D) rounds, as the tree has depth O(D)O(D).

The following lemmas refer to the values of up and down at the end of the execution of the algorithm. We denote by TvT_v the subtree of TT rooted at vv.

Lemma 28. up[vv] = true if and only if a node in TvT_v is in the 2-core of GG.

Proof. If up⁡[v]=true\operatorname{up}[v] = \mathit{true}, then there is a descendant (in TT) of vv incident to a non-tree edge. This descendant, which is a node of TvT_v, is in a cycle in GG, and thus is in the 2-core of GG. On the other hand, if vv is in the 2-core of GG, then let uu be a descendant of vv in the 2-core with maximum depth in TT. Each of the at least two edges in the 2-core incident to uu does not go to a descendant of uu. Therefore, at least one of these edges is not in TT, and hence up⁡[v]=up⁡[u]=true\operatorname{up}[v] = \operatorname{up}[u] = \mathit{true}. ◇

Lemma 29. up⁡[v]=down⁡[v]=true\operatorname{up}[v] = \operatorname{down}[v] = \mathit{true} if and only if vv is in the 2-core of GG.

Proof. The proof is by induction on the depth of vv in TT. First, assume up⁡[v]=down⁡[v]=true\operatorname{up}[v] = \operatorname{down}[v] = \mathit{true}. If v≠sv \ne s and down⁡[p[v]]=true\operatorname{down}[p[v]] = \mathit{true}, then up⁡[p[v]]=true\operatorname{up}[p[v]] = \mathit{true} because up⁡[v]=true\operatorname{up}[v] = \mathit{true}, and, by induction, p[v]p[v] is in the 2-core of GG. By Lemma 28, there is also a path in TvT_v from vv to a node in the 2-core. So, there are two edge-disjoint paths from vv to vertices in the 2-core, which implies that vv is also in the 2-core. If v=sv = s or down⁡[p[v]]=false\operatorname{down}[p[v]] = \mathit{false}, then, as down⁡[v]=true\operatorname{down}[v] = \mathit{true}, vv must have two children uu and ww such that up⁡[u]=up⁡[w]=true\operatorname{up}[u] = \operatorname{up}[w] = \mathit{true}. By Lemma 28, there are two edge-disjoint paths from vv to vertices in the 2-core. So, vv is in the 2-core of GG.

Now, assume vv is in the 2-core of GG. By Lemma 28, up⁡[v]=true\operatorname{up}[v] = \mathit{true}. If v≠sv \ne s and p[v]p[v] is in the 2-core, then, by induction, down⁡[p[v]]=true\operatorname{down}[p[v]] = \mathit{true}, and hence down⁡[v]=true\operatorname{down}[v] = \mathit{true}. If v=sv = s or p[v]p[v] is not in the 2-core, then no non-tree edge is incident to vv, because in a BFS tree the fundamental cycle of a non-tree edge vuvu always includes p[v]p[v]. There are at least two edges vuvu and vwvw in the 2-core, and uu and ww must be distinct children of vv, since p[v]p[v] is not in the 2-core. By Lemma 28, up⁡[u]=up⁡[w]=true\operatorname{up}[u] = \operatorname{up}[w] = \mathit{true}, thus down⁡[v]=true\operatorname{down}[v] = \mathit{true}. ◇

This finishes the proof of correctness of the algorithm. ◻

We have thus shown precisely the threshold of hardness of degeneracy problems in CONGEST. While 2-Core (and 1-Degenerate) can be solved efficiently (i.e., they need O(D)O(D) rounds), 3-Core (and 2-Degenerate) cannot (i.e., they need Ω~(D+n)\widetilde{\Omega}(D + \sqrt{n}) rounds).

Conclusion

We provided a series of lower bounds on the round complexity of computing the degeneracy of a network in CONGEST. We established unconditional lower bounds showing that, for any k≥2k \ge2, solving kk-Degenerate requires Ω~(D+n)\widetilde{\Omega}(D + \sqrt{n}) rounds, even with a randomized algorithm, and even for (2−ε)(2 - \varepsilon)-approximation. Furthermore, we provided conditional lower bounds suggesting that the problem is likely even harder. Specifically, we showed that algorithms running in O(n1−ε)O(n^{1-\varepsilon}) rounds would imply significant breakthroughs in complexity theory, such as the circuit value problem admitting a polynomial parallel speedup, unless they consume high local computation time. These results provide strong evidence that computing the degeneracy requires Ω~(n)\widetilde{\Omega}(n) rounds, even in networks of constant maximum degree and logarithmic diameter.

An interesting open problem is to close the gap between our unconditional polynomial lower bounds and the straightforward linear upper bound. Another possible path forward is to generalize the lower bounds. We note in § 3.1.3 that our lower bounds hold for other graph problems, such as LEXMIS, LEXCOL, and MAXFLOW. Properly formalizing the subset of P-complete problems for which our conditional or unconditional lower bounds hold would make clear which results from P-completeness translate (totally or partially) to the CONGEST model, allowing us to reuse established theoretical results from complexity theory instead of having to prove them all over again in the CONGEST model. Similar lower bounds for P-complete problems have also emerged from other models, such as the semi-streaming model [6] and the dynamic graph model [16], and this generalization could benefit those areas as well.

References

  1. [1]Abboud, A., Censor-Hillel, K., Khoury, S., Paz, A.: Smaller cuts, higher lower bounds. ACM Trans. Algorithms 17(4), 30:1–30:40 (2021)arxiv.org/abs/1901.01630
  2. [2]Aksu, H., Canim, M., Chang, Y.C., Korpeoglu, I., Ulusoy, Ö.: Distributed k-core view materialization and maintenance for large dynamic graphs. IEEE Transactions on Knowledge and Data Engineering 26(10), 2439–2452 (2014)DOI
  3. [3]Alvarez-Hamelin, J., Dall’Asta, L., Barrat, A., Vespignani, A.: Large scale networks fingerprinting and visualization using the k-core decomposition. Advances in Neural Information Processing Systems 18 (2005)
  4. [4]Anderson, R., Mayr, E.W.: A P-complete problem and approximations to it. Tech. rep., Stanford University (1984)
  5. [5]Aridhi, S., Brugnara, M., Montresor, A., Velegrakis, Y.: Distributed k-core decomposition and maintenance in large dynamic graphs. In: 10th ACM Int. Conference on Distributed and Event-Based Systems (DEBS). pp. 161–168 (2016)DOI
  6. [6]Assadi, S., Chen, Y., Khanna, S.: Polynomial pass lower bounds for graph streaming algorithms. In: 51st Annual ACM Symposium on Theory of Computing (STOC). pp. 265–276 (2019)arxiv.org/abs/1904.04720
  7. [7]Assadi, S., Ghosh, P., Loff, B., Mittal, P., Mukhopadhyay, S.: Polynomial pass semi-streaming lower bounds for k-cores and degeneracy. In: 39th Computational Complexity Conference (CCC). LIPIcs, vol. 300, pp. 7:1–7:16 (2024)arxiv.org/abs/2405.14835
  8. [8]Bader, G.D., Hogue, C.W.: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4(1), 2 (2003)pubmed.ncbi.nlm.nih.gov/12525261
  9. [9]Barenboim, L., Elkin, M.: Distributed graph coloring: Fundamentals and recent developments (2013)DOI
  10. [10]Batagelj, V., Zaversnik, M.: An O(m) algorithm for cores decomposition of networks (2003), http://arxiv.org/abs/cs/0310049
  11. [11]Bhawalkar, K., Kleinberg, J.M., Lewi, K., Roughgarden, T., Sharma, A.: Preventing unraveling in social networks: The anchored k-core problem. In: 39th Int. Colloq. on Automata, Languages, and Programming (ICALP). LNCS, vol. 7392, pp. 440–451 (2012)
  12. [12]Bondy, J., Murty, U.: Graph Theory. Springer (2008)
  13. [13]Carmi, S., Havlin, S., Kirkpatrick, S., Shavitt, Y., Shir, E.: A model of internet topology using k-shell decomposition. Proceedings of the National Academy of Sciences 104(27), 11150–11154 (2007)pubmed.ncbi.nlm.nih.gov/17586683
  14. [14]Chan, T.H.H., Sozio, M., Sun, B.: Distributed approximate k-core decomposition and min-max edge orientation: breaking the diameter barrier. In: IEEE Int. Parallel and Distributed Processing Symp. (IPDPS). pp. 345–354 (2019)
  15. [15]Condon, A.: A theory of strict P-completeness. Computational Complexity 4(3), 220–241 (1994)
  16. [16]Couto, Y.S., Fernandes, C.G.: Hardness of dynamic core and truss decompositions. In: Approximation and Online Algorithms (WAOA). LNCS, vol. 16077, pp. 64–80 (2026)DOI
  17. [17]Czygrinow, A., Hańćkowiak, M., Szymańska, E.: Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs. In: International Symposium on Algorithms and Computation. pp. 668–678. Springer (2009)DOI
  18. [18]Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: 43rd Annual ACM Symp. on Theory of Computing (STOC). p. 363–372 (2011)
  19. [19]Dory, M., Ghaffari, M., Ilchi, S.: Near-optimal distributed dominating set in bounded arboricity graphs. In: ACM Symposium on Principles of Distributed Computing (PODC). pp. 292–300 (2022)
  20. [20]Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: 33rd ACM Symp. on Principles of Distributed Computing (PODC). pp. 367–376 (2014)DOI
  21. [21]Emerson, A.I., Andrews, S., Ahmed, I., Azis, T.K.A., Malek, J.A.: k-Core decomposition of a protein domain co-occurrence network reveals lower cancer mutation rates for interior cores. J. of Clinical Bioinformatics 5(1) (2015)DOI
  22. [22]Parallel and streaming algorithms for k-core decompositionarxiv.org/abs/1808.02546
  23. [23]Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27(1), 302–316 (1998)DOI
  24. [24]Ghaffari, M., Lymouri, C.: Simple and near-optimal distributed coloring for sparse graphs. arXiv:1708.06275 (2017)arxiv.org/abs/1708.06275
  25. [25]Giatsiadis, C., Thilikos, D.M., Vazirgiannis, M.: Evaluating cooperation in communities with the k-core structure. In: Int. Conf. on Advances in Social Networks Analysis and Mining. pp. 87–93. IEEE (2011)
  26. [26]Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, New York (1995)DOI
  27. [27]Guo, B., Zhao, R.: Experimental evaluation of distributed k-core decomposition (2025)arxiv.org/abs/2406.17580
  28. [28]Haeupler, B., Wajc, D., Zuzic, G.: Network Coding Gaps for Completion Times of Multiple Unicasts. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). pp. 494–505. IEEE, Durham, NC, USA (Nov 2020)arxiv.org/abs/1905.02805
  29. [29]Haeupler, B., Wajc, D., Zuzic, G.: Universally-optimal distributed algorithms for known topologies. In: 53rd Annual ACM SIGACT Symposium on Theory of Computing. pp. 1166–1179. ACM, Virtual Italy (Jun 2021)arxiv.org/abs/2104.03932
  30. [30]Hirvonen, J., Suomela, J.: Distributed Algorithms (2020). https://jukkasuomela.fi/da2020/da2020.pdf
  31. [31]Kitsak, M., Gallos, L.K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H.E., Makse, H.A.: Identification of influential spreaders in complex networks. Nature Physics 6(11), 888–893 (2010)
  32. [32]Korhonen, J.H., Rybicki, J.: Deterministic Subgraph Detection in Broadcast CONGEST. LIPIcs, Volume 95, OPODIS 2017 95, 4:1–4:16 (2018)arxiv.org/abs/1705.10195
  33. [33]Kothapalli, K., Pemmaraju, S.: Distributed graph coloring in a few rounds. In: 30th annual ACM symposium on Principles of distributed computing (PODC). pp. 31–40 (2011)DOI
  34. [34]Kruskal, C.P., Rudolph, L., Snir, M.: A complexity theory of efficient parallel algorithms. Theoretical Computer Science 71(1), 95–132 (1990)
  35. [35]Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms 28(1), 40–66 (1998)
  36. [36]Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)DOI
  37. [37]Mak, L.: Parallelism always helps. SIAM J. Comput. 26(1), 153–172 (1997)DOI
  38. [38]Malliaros, F.D., Giatsiadis, C., Papadopoulos, A.N., Vazirgiannis, M.: The core decomposition of networks: Theory, algorithms and applications. The VLDB Journal 29(1), 61–92 (2020)DOI
  39. [39]Mandal, A., Hasan, M.A.: A distributed k-core decomposition algorithm on spark. In: 2017 IEEE International Conference on Big Data (Big Data). pp. 976–981 (2017). https://doi.org/10.1109/BigData.2017.8258018
  40. [40]Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. of the ACM 30(3), 417–427 (1983)DOI
  41. [41]Mittal, P.: How to Color Graphs, and How Not to Chase Pointers. Ph.D. thesis, University of Waterloo (May 2026)
  42. [42]Montresor, A., De Pellegrini, F., Miorandi, D.: Distributed k-core decomposition. In: 30th ACM Symp. on Principles of Distributed Computing (PODC). pp. 207–208 (2011)
  43. [43]Morone, F., Burleson-Lesser, K., Vinūtha, H.A., Sastry, S., Makse, H.A.: The jamming transition is a k-core percolation transition. Physica A: Statistical Mechanics and its Applications 516, 172–177 (2019)DOI
  44. [44]Morone, F., Del Ferraro, G., Makse, H.A.: The k-core as a predictor of structural collapse in mutualistic ecosystems. Nature Physics 15(1), 95–102 (2019)DOI
  45. [45]Nikabadi, A., Korhonen, J.H.: Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters. LIPIcs, Volume 217, OPODIS 2021 217, 15:1–15:18 (2022)
  46. [46]Nisan, N., Wigderson, A.: Rounds in communication complexity revisited. In: 23rd Annual ACM Symp. on Theory of Computing (STOC). pp. 419–429. ACM Press, New Orleans, Louisiana, United States (1991)
  47. [47]O’Brien, M.P., Sullivan, B.D.: Locally estimating core numbers. In: IEEE Int. Conf. on Data Mining. pp. 460–469 (2014)
  48. [48]Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (2000)DOI
  49. [49]Rao, A., Yehudayoff, A.: Communication complexity: and applications. Cambridge University Press (2020)
  50. [50]Seidman, S.B.: Network structure and minimum degree. Social Networks 5(3), 269–287 (1983)DOI
  51. [51]Williams, R.: Parallelizing time with polynomial circuits. Theory of Computing Systems 48(1), 150–169 (2011)
  52. [52]Wood, C.I., Hicks, I.V.: The minimal k-core problem for modeling k-assemblies. The Journal of Mathematical Neuroscience 5(1), 14 (2015)DOI

Paper details

vlnc:W_zrz7txet
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents