WorksComputer Science
Lower Bounds for the Distributed Computation of Degeneracy and k-Core
Abstract
The degeneracy of a graph is the maximum integer such that has a non-empty -core, where the -core is the largest induced subgraph with minimum degree . Computing the -core of a graph 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 for which the node belongs to the -core, is computed in rounds in -node networks, where adjacent nodes exchange only bits at each round, i.e., in the standard CONGEST model. However, while rounds is a trivial lower bound for these problems in networks of diameter , this does not rule out the existence of an algorithm running in 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 rounds. Specifically, our first main result states that, for any , approximating the degeneracy up to a multiplicative factor requires rounds in CONGEST even in networks of diameter , and still 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 , deciding whether a graph is 2-degenerate cannot be solved in rounds with -time parallel local computation per round at each node.
Introduction
General Objective
Finding the degeneracy of a graph is a subproblem of the -core decomposition problem. Recall that a graph is called -degenerate if every subgraph of has a vertex of degree at most . The minimum for which is -degenerate is called the degeneracy of , denoted by . 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 , if denotes its degeneracy, and its arboricity, then . 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 -core of is the largest induced subgraph of that has minimum degree at least . Note that the -core is well-defined and unique as, for any two sets of nodes and , if the induced subgraphs and satisfy the degree condition, then so does . If has a nonempty -core, then is not -degenerate, that is, . More precisely, the degeneracy of is the maximum for which it has a nonempty -core. Given a node of a graph , the core value of is the largest such that belongs to the -core of . The concept of -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 , 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 of the network.
For , the -ApproxDegeneracy problem asks each node to output an -approximation of the degeneracy, that is, every node must output a value such that .
For , the -Degenerate problem asks all nodes to output “accept” if the network is -degenerate, and at least one node must output “reject” otherwise.
For , the -Core problem asks each node to output “yes” if it is in the -core of the network, and “no” otherwise.
The CoreValue problem asks each node to output the largest integer for which it belongs to the -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 -node network, nodes are given distinct identifiers (IDs) in a polynomial range, i.e., each ID consumes bits to be stored. Computation is performed as a sequence of synchronous rounds. Specifically, all nodes of an -node network start at the same time and, at each round, every node (1) sends an -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 at round may only be known, at round , to the nodes in the radius- ball around in the network, and a node can send and receive 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 rounds8 [20], and “global problems” such as computing a minimum-weight spanning tree (MST) require rounds on networks of diameter [48]. Nevertheless, many networks coming from practical situations have sublinear diameter, so CONGEST algorithms running in rounds on -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 rounds [23, 35]. Our main goal is to figure out whether computing degeneracy or -core decomposition also admits CONGEST algorithms running in rounds on networks with sublinear diameter, or whether they are “hard” in the sense that they require rounds, regardless of the diameter.
Solving -DEGENERATE in CONGEST suffers from the same limitation as when computing an MST, even for . Indeed, solving 1-DEGENERATE requires rounds on networks of diameter , 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 on -node graphs with 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 rounds on -node networks. The main goal of this paper is to close the gap between these two bounds and . 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 rounds on -node networks with diameter ?
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 -DEGENERATE (if then all nodes accept whenever , and all nodes reject otherwise). Similarly, an algorithm solving -CORE also solves -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 -CORE. For -CORE, the answer is direct. For DEGENERACY, it suffices to find the maximum core value, which can be done in additional rounds. Overall, among the problems in Definition 1, and letting aside the approximated variants, the easiest problem is -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, -CORE, and -DEGENERATE as well) in rounds on -node networks — see [14]. The resulting distributed algorithm may however take 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 rounds. This will contrast with our lower bounds for -DEGENERATE when . Note that the dependence on for 2-CORE is optimal in the sense that any algorithm solving 2-CORE must run in rounds.
Our algorithm relies on the fact that a node 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 .
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 rounds on networks of diameter is unlikely, and that a round complexity is in fact unconditionally impossible even in networks of diameter . Our 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 rounds for any CONGEST algorithm computing the degeneracy of the network. More specifically, we show that, under the CONGEST() model, that is, under the general version of CONGEST in which every two neighbors can exchange -bit messages at each round, deciding 2-DEGENERATE on -node networks of diameter requires rounds. In particular, in CONGEST, deciding 2-DEGENERATE requires rounds even in networks of diameter , and rounds in networks of constant diameter.
These lower bounds hold even for randomized Monte-Carlo algorithms that succeed with probability . In fact, they also hold for the approximation variant of the problem. Specifically, we show that, for any , -APPROXDEGENERACY requires rounds to be solved in -node networks of diameter under the CONGEST() model. In particular, for every fixed , -APPROXDEGENERACY requires rounds in CONGEST even in networks of diameter , and 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 , 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 -round lower bound for DEGENERACY, by a reduction from the pointer chasing problem; Still, this bound is worse than our lower bound.)
Conditional Lower Bounds Our unconditional lower bound on the number of rounds demonstrates that there cannot exist super-efficient algorithms computing the degeneracy of networks (e.g., in polylog rounds). However, this bound does not prevent the existence of a sublinear algorithm, i.e., running in rounds for some . 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 -node networks, if there exists a CONGEST algorithm solving 2-DEGENERATE in rounds with parallel computation time per round at each node (on a PRAM with poly processors), then 2-DEGENERATE can be solved by a PRAM algorithm that runs in time using poly processors.
A direct consequence of this theorem is that 2-Degenerate requires rounds in -node networks of diameter under the CONGEST model with parallel computation time per round at every node whenever , 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 at every node in -node graphs of constant maximum degree corresponds to exponential time with respect to the amount of information received at each round by each node. Our result holds for computation power beyond LOGSPACE, up to 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 -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 -coloring graphs of maximum degree , 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 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 admits a polynomial parallel speedup if there exists a parallel algorithm that uses a polynomial number of processors and runs in time , with for some . 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 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 . 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 -core in distributed and parallel systems. With respect to parallel computation, Anderson and Mayr [4] showed that computing the -core is P-complete, that there exists a -approximation for -core in NC, and that no -approximation in NC exists unless P = NC. In the context of distributed systems, the study of core values was initiated in [42]. An -round -approximation algorithm for computing the core values in CONGEST was designed in [14], where it is also proved that any -approximation needs rounds, and any -approximation needs rounds. Our lower bounds for 2-DEGENERATE also hold for -approximation algorithms computing the core values, and are actually stronger. Several other works developed distributed algorithms for -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 -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 -approximations for degeneracy. While these parameterized algorithms are efficient (in low degeneracy graphs), and while a -approximation is enough for their use case, the dependency on the computed approximation degeneracy of the actual degeneracy may be exponential, as in the rounds for finding induced tree subgraphs on 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 -approximation for every core value using space is presented in [22]. In contrast, any semi-streaming algorithm for exactly solving this problem requires passes [7]. Regarding dynamic graph algorithms, [16] established conditional lower bounds for the -core problem. Namely, assuming well-established conjectures, the -core problem requires time per update or query on a graph with edges. O’Brien and Sullivan [47] presented an algorithm that estimates the core value of every node based on local information within a ball of bounded radius centered at . The algorithm provides an asymptotic error bound for the core value estimation on Erdős–Rényi random graphs.
Preliminaries
CONGEST Model
The CONGEST() model [48] is a classical model of distributed computation represented by a connected simple graph , where each node executes the same algorithm in synchronous rounds, and the nodes collaborate to solve a graph problem defined on . Every node has an identifier, which is unique in the network. It is assumed that, in an -node network, each identifier can be stored in bits. Additionally, every node 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 -CORE, it must output yes or no depending on whether it belongs to the -core of the network.
The defining feature of the CONGEST() 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 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() with , 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(), that is, there are no restrictions on the size of the messages exchanged. In particular, every (computable) graph problem is solvable in rounds under the LOCAL model in networks of diameter , 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 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 , 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 ()-Coloring
Our lower bounds for degeneracy and -core also apply to other problems such as, prominently, computing maximum flows.
Maximum Flow
Let be a directed graph, let be the arc capacities, and let and be the source and sink vertices, respectively. A flow in is a mapping . A flow is feasible if for each arc , and for each . The MAXFLOW problem asks to compute a feasible flow that maximizes . 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 ()-coloring. The study of such problems is standard in the context of parallel complexity [26]. In all these variants, we assume that every node of the graph is given a number as input, which is assumed to be unique.
Recall that an independent set in is a set of pairwise non-adjacent vertices of , and that an independent set is maximal if no vertex can be added to it while maintaining the independent set property. Let be a maximal independent set with . The ordered sequence is called the signature of . The LexMIS problem asks to compute the maximal independent set of that has the smallest signature, where signatures are lexicographically ordered as words on the alphabet . In CONGEST, each node must output 1 if it is in the MIS, and 0 otherwise.
A -coloring of is an assignment such that for each . The lexicographic variant of -coloring is defined similarly, where denotes the maximum degree of . Let with . Given a -coloring of , the ordered sequence is called the signature of the coloring . The LexCol problem asks to compute the -coloring of that has the smallest signature, when signatures are compared lexicographically as words on the alphabet . 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 , , and , let be the graph consisting of paths, each with nodes, plus a complete -ary tree of depth and leaves. The th leaf of is connected to the th vertex in each of the paths. We denote by and the first and last leaves of . See Figure 1 for an illustration. The graph has nodes, and diameter .
Figure 1. The graph for , , and , that is, .
Our lower bound in CONGEST follows from the lower bound for the set-disjointness problem in communication complexity. Given an integer , the -disjointness problem in , denoted by , is defined as follows. Nodes and are respectively given inputs and . The goal is for and to decide whether and are disjoint, that is, whether for all . Both nodes must accept if and are disjoint, and both of them must reject otherwise. Our lower bound is based on the following result.
Lemma 2 ([18]). For any , and , on with requires rounds to be solved in , even by a randomized Monte-Carlo algorithm succeeding with probability .
To obtain a lower bound for 2-Degenerate, we show that any algorithm for this problem can be used to solve on . This will require to modify the network , but we shall later argue how our modifications can be simulated by the nodes of the original . Our construction is based on the following graph family. For any integers , any binary strings , and any integer , the graph is obtained by modifying . The construction uses the gadget depicted on Figure 2, referred to as the flyswatter gadget. Copies of this gadget are attached to vertices of according to the following rules.
Figure 2. The flyswatter gadget. If the gadget is attached to a node in , then the node is the node depicted by the dotted circle on the figure.
For every , if then attach a flyswatter to the first node of the th path.
For every , if then attach a flyswatter to the last node of the th path.
Attach a flyswatter to each leaf of the tree in , as well as to its root.
As the number of nodes in is at most a constant factor larger than the number of nodes in , and as its diameter increases by at most twice the diameter of the flyswatter, the following holds:
Observation 3. has nodes, and diameter .
The way the flyswatters are attached to as a function of and enables one to relate the degeneracy of to the truth value of the disjointness of and .
Lemma 4. is 2-degenerate if and only if and are disjoint.
Proof. Suppose first that is 2-degenerate, i.e., every subgraph of has a vertex of degree at most 2. Let be the subgraph of containing its th path, the tree of , and all flyswatters attached to those vertices. Note that all internal vertices of the th path, all the vertices in , and all vertices in the flyswatters have degree at least 3 in , independently of the values of and . For every , since is 2-degenerate, there must be a vertex of with degree at most 2, which implies that at least one of the two endpoints of the th path is not connected to a flyswatter. It follows that or , and thus and are disjoint.
Let us now suppose that is not 2-degenerate, meaning that has a nonempty 3-core . A flyswatter can have either all its vertices in the 3-core , or none of them. That is, a flyswatter belongs to if and only if it is attached to a vertex that belongs to . Also, cannot be completely contained in the tree . It follows that must contain some vertex from at least one of the paths, as otherwise would be empty. A consequence of the fact that contains at least one vertex from one of the paths is that must contain all the neighbors of because the vertices in the paths have degree at most 3 in . It follows that must actually contain a complete path, say the th path, for some . In particular, the endpoints of that path must have degree 3, which implies that they are both attached to a flyswatter. This means that , and thus and are not disjoint. □
Now, we show how to transform an algorithm for 2-DEGENERATE into an algorithm for DISJ, while controlling its round complexity.
Lemma 5. If there exists an algorithm solving 2-DEGENERATE on -node networks of diameter in rounds under CONGEST, then there exists an algorithm solving DISJ on in rounds under CONGEST. Moreover, if is a randomized Monte Carlo algorithm succeeding with probability at least , then so is .
Proof. Suppose that there is an algorithm for 2-DEGENERATE as in the statement. We describe an algorithm for DISJ on . In the first round of , for each , node sends to the first node of the th path, and node sends to the last node of the th path.
At this point, every node has enough information to determine whether it is attached to a flyswatter gadget in the construction of , and so can simulate the virtual execution of on in the actual network . In particular, any node 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 . From the second round, is thus the mere simulation of on the virtual network .
At the end of the simulation, the nodes output the result of , i.e., whether is 2-degenerate or not. More specifically, if is 2-degenerate then all nodes accept, and if is not 2-degenerate, then at least one node rejects. To guarantee that both and reject in case is not 2-degenerate, any rejecting node floods its opinion throughout the network, in diameter rounds. By Lemma 4, this algorithm correctly computes whether and are disjoint.
As far as the round complexity of is concerned, note that its first round communicates at most one bit per edge, so this round is valid in CONGEST for any . The simulation in of the execution of on takes rounds because has nodes (cf. Observation 3). By Observation 3, the final flooding consumes additional rounds. Since , we have for any , implying that takes rounds. □
Theorem 6. For any , deciding 2-DEGENERATE on -node networks of diameter requires rounds in the CONGEST model. This holds even for randomized Monte-Carlo algorithms succeeding with probability at least .
Proof. Suppose that there is a randomized CONGEST algorithm for 2-DEGENERATE on -node networks running in rounds, where . By Lemma 5, there is a randomized algorithm for DISJ on the network running in rounds. By Lemma 2, we obtain , when . Since the number of nodes in the network is , and since , expressing in terms of yields , as claimed. □
Corollary 7. Deciding 2-DEGENERATE on -node networks of diameter requires rounds in CONGEST, and deciding 2-DEGENERATE on -node networks of diameter requires 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 for every and . Our construction guarantees that the degeneracy of changes by a large factor depending on whether and are disjoint, which allows us to use any -approximation for the degeneracy to solve , 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 the stable graph on vertices. We define as the graph obtained from by using the gadget depicted in Figure 3 referred to as the fishnet gadget . This gadget graph consists of copies of connected in sequence (i.e., every vertex of the th copy is connected to all vertices of the th copy, and to all vertices of the th copy). Moreover, the th node of the first copy of is connected to the th node of all the other copies. The connection of a fishnet gadget to the graph is achieved via the nodes of the last copy of (see Figure 3).
Figure 3. The fishnet gadget for , connected to whose vertices are the three to the right, represented by dotted circles.
The graph is obtained from as follows:
Each vertex in a path of is replaced by a copy of the stable graph .
Each path edge is replaced by edges connecting all vertices of to .
Each edge from a leaf to a path vertex is replaced by edges connecting to all vertices in .
For each , if then a fishnet is attached to the first copy of in the th path, and if then a fishnet is attached to the last copy of in the th path.
Figure 4 provides an example of .
Figure 4. The graph for , , , , , and , built from shown in Figure 2.
The interest of the graph is that its degeneracy differs a lot depending on whether and are disjoint.
Lemma 8. The degeneracy of satisfies if and are disjoint, and otherwise.
Proof. Let us first assume that and are disjoint, and let us assume for the purpose of contradiction that contains a nonempty -core . Note that cannot be contained entirely in a fishnet because has minimum degree if it is not attached to the graph . Similarly cannot be entirely contained in the tree of . As a consequence, must contain a vertex of some copy of in some path. Let us say that belongs to the th copy of in the th path, for some and . On the one hand, node has at least neighbors in . On the other hand, in , node has one incident edge connecting it to the tree , at most neighbors to its left11 and, analogously, at most neighbors to its right. It follows that, in , must have at least one neighbor to each side. Repeating this argument yields a contradiction, since or , meaning at least one of the endpoints of the th path is not attached to a fishnet. As a consequence, the -core of is empty, and thus .
Conversely, if and are not disjoint, then there exists such that . Let be the subgraph of consisting of all copies of in the th path, and the fishnets attached to its first and last copies of . Note that has minimum degree because, when connected to , a fishnet has minimum degree . This implies that the -core of is not empty, and thus .
Lemma 9. If there exists an algorithm solving -ApproxDegeneracy on -node networks with diameter in rounds under CONGEST(B), then there exists an algorithm solving Disj on in rounds under CONGEST(B). Moreover, if is a randomized Monte-Carlo algorithm succeeding with probability , then so is .
Proof. Suppose that there is an algorithm for -ApproxDegeneracy as in the statement. For designing , let to be specified later. We proceed as in the proof of Lemma 5, merely using instead of . In particular, the information needed to determine how to simulate , which depends only on and can be sent by and to their neighbors in a single round. Furthermore, the nodes can simulate the virtual graph on the actual network . Specifically, each vertex of needs to simulate nodes, and each edge of is mapped to edges of . So, each round of can be simulated in rounds of . Note that has nodes (and edges), and therefore it has nodes. Also, it has diameter . Therefore, the total running time of is .
An appropriate choice of is because this choice guarantees that . Let be any -approximation to the degeneracy of computed by any node, that is, . By Lemma 8, if and are not disjoint then , implying . If and are disjoint, and if , then . Thus if then and are disjoint, and otherwise they are not, proving the correctness of .
Theorem 10. Let , , and . Solving -ApproxDegeneracy on -node networks with diameter requires rounds in the CONGEST model. This holds even for randomized Monte-Carlo algorithms succeeding with probability .
Proof. Suppose that there is a (randomized) algorithm solving -ApproxDegeneracy on -node networks in rounds. By Lemma 9, there is a (randomized) algorithm for Disj on running in rounds. By Lemma 2, we get , when . Now, for the appropriate , the number of nodes in is . As , expressing in terms of yields , as claimed.
Corollary 11. For any fixed1 , solving -ApproxDegeneracy on -node networks of diameter requires rounds in CONGEST, and solving -ApproxDegeneracy on -node networks with constant diameter requires rounds.
Conditional Lower Bounds
Based on the lower bounds from Section 3, one might be tempted to design an , or even an -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 running in time on inputs of size admits a polynomial parallel speedup [34] if there exist and a PRAM algorithm that implements so that runs in time using polynomially many processors, where . 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 time. Moreover, the problem is P-complete, that is, a time parallel algorithm is unlikely to exist. In fact, no time parallel algorithm is known, for any , 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 -round CONGEST algorithm has local parallel time if it terminates in at most rounds and, at every node, and at every round, the node runs in time using processors on a PRAM for computing its new states and the messages to be sent. Let be a decision problem in graphs (e.g., 2-Degenerate). For solving 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 holds. In the PRAM model the algorithm must simply accept or reject, according to whether holds or not.
Lemma 12. Let be a class of graphs, and let be a decision problem in graphs. If there exists a CONGEST algorithm for in , running on -node graphs in rounds, with local parallel computation time in the PRAM model, then there exists a PRAM algorithm for in that runs in time using processors.
Proof. Let be a CONGEST algorithm for in , as in the statement. For sufficiently large , there exists a constant such that, when running on an -node network, each node uses at most processors. We split each round of into two phases: computation, and communication. At the beginning of round , each node is in a memory state , and holds a list of messages 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 , node uses and for computing a set of messages , to be sent to its neighbors, and updates its memory state from to . In the communication phase, the messages are delivered.
We define the desired PRAM algorithm as follows. Let be an -node instance of . Algorithm stores , , and , and uses processors for each node of . In addition, uses other processors, for simulating the communication phase of .
During the computation phase of round , emulates (in parallel) the local computation of the CONGEST algorithm . Each node , starting from the memory state , and using the incoming messages in , computes and in time using its processors. The PRAM algorithm uses processors for simulating this phase.
During the communication phase of round , processor overwrites from with , which takes time. Overall, this process transforms the stored into for all . After this, is ready to start the simulation of round of the CONGEST algorithm .
At the end of the simulation (i.e., when all nodes have terminated), checks the output of each node, and accepts if and only if all nodes have accepted. This operation can be performed by in time. In total, uses processors, and takes 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 . It follows that in admits a PRAM algorithm that, on -node graphs from , runs in time using processors.
As a consequence, the existence of a “fast” algorithm for in CONGEST implies the existence of a “fast” PRAM algorithm for . 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 and be two graph decision problems. We say has a quasi-linear NC-reduction to , denoted by , if there is a function from the set of graphs to the set of graphs such that, for every graph ,
accepts if and only if accepts ,
is computable in NC,
, and
, where denotes the diameter of graph .
Lemma 13. Let be a decision problem such that . Unless CVP admits a polynomial parallel speedup, it holds that, for every and , does not admit a CONGEST algorithm running in rounds with local parallel computation time in -node networks of diameter .
Proof. Let us assume that there exists a CONGEST algorithm for as in the statement. Then, by Lemma 12, there exists a PRAM algorithm for that runs in time using processors. Consider any instance of size 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 , and constant diameter. Moreover, it has the same circuit value. Using the reduction from CVP to , one can in time construct an -node graph of diameter that is an instance of such that accepts if and only if the circuit value of is 1. One can solve the instance with the PRAM algorithm , which runs in time using processors. This implies that CVP admits a polynomial parallel speedup, as .
Theorem 14. Let and . Unless CVP admits a polynomial parallel speedup, 2-Degenerate does not admit a CONGEST algorithm running in rounds with local parallel computation time on -node networks, even on graphs of maximum degree 4 and diameter .
Proof. Consider the monotone fan-in 2 fan-out 2 restriction to the circuit value problem, referred to as M2CVP. From any instance of CVP, one can construct an instance 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 has size and diameter , then has size and diameter . 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 with nodes, maximum degree 4, and diameter . It follows that 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 for any . Thus it allows the existence of an algorithm running in rounds if it has 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 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 bits on each of its incident edges per round. Thus, in networks of constant degree, the total number of bits a node receives during rounds is . Roughly speaking, as a function of the input size, time corresponds to exponential time for , and to sublinear time only for .
Second, in networks with constant degree, for most known algorithms, the local memory state of each node can be encoded in bits throughout their whole execution, and the computation performed at each node is often elementary (e.g., computing the minimum or maximum of integers, performing a constant number of XOR operations on -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 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 time on a PRAM with processors. Even for , 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 satisfy . The same lower bound as in Theorem 14 can be derived for these problems. This is for instance the case of -ApproxDegeneracy, and of other variants of -Core such as directed -cores, and -truss, which is the variant of -core in which each edge in the -truss must be part of 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 and . Unless CVP admits a polynomial parallel speedup, none of the problems LexMIS, LexCol, and MaxFlow admit a CONGEST algorithm running in rounds with local parallel computation time in -node networks of diameter .
MaxFlow has a known unconditional lower bound of [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 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 if there exists a reduction from M2CVP to which roughly preserves the graph structure, so that the “simulation argument” of Lemma 5 still works. This is the case for several variants of -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 is mapped to a (constant-size) subgraph , and if has an edge to in the final graph, then is connected to 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 . 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 , 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 make disjointness hard to solve. Given any graph , the parameter is defined as the maximum distance for which there exists a set of connectable source-sink pairs (i.e., vertex pairs that can be connected by vertex-disjoint paths in ) and an edge-length assignment satisfying:
For the -vertex graph , we have
This lower bound is the source of the difficulty of computing in (cf. Lemma 2). For several CONGEST problems, the framework in [29] enables one to derive the lower bound of rounds for every graph . Nevertheless, this lower bound does not hold for DEGENERACY. Indeed, the distributed peeling algorithm for 2-DEGENERATE takes rounds in the graph 12, which has diameter . As a consequence, 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 . 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 . It involves two players, referred to as Alice and Bob. Alice receives an input and Bob receives input . The goal of the players is to output . The communication complexity of is the number of bits the two players must exchange in the worst instance. It is denoted by , or if randomization is allowed. The following definition is borrowed from [1].
Definition 16. Let be a function, and let be a graph predicate. A family of graphs with a partition , and possibly labels on the vertices and edges, is said to be a family of lower bound graphs w.r.t. and if the following properties hold:
only the edges in and their labels may depend on ;
only the edges in and their labels may depend on ;
is uniquely determined by whether satisfies the predicate .
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 be a function, and let be a graph predicate. If there exists a family of lower bound graphs w.r.t. and with and , then every distributed algorithm for deciding requires rounds in the CONGEST model, and every randomized algorithm requires rounds.
Why the Framework of Small Cuts Fails for Degeneracy
Let be a function. If it is possible to use an algorithm for -DEGENERATE to decide, given any , whether , that is, if there exists a family of lower bound graphs w.r.t. and -DEGENERATE, then we will show an efficient communication protocol for . This implies that the communication complexity is low and, hence, Theorem 17 yields only trivial lower bounds for -DEGENERATE. Recall that, in the peeling algorithm, the vertices with degree at most are progressively removed from the input graph , until no vertices have degree at most . In the end, the remaining graph is precisely the -core of , and is -degenerate if and only if the -core is empty. The order in which the vertices are peeled (which may not be unique) is called a peeling order for the -core. With this in mind, we can show the communication protocol.
Theorem 18. Let be an integer, and let be a function. If there exists a family of lower bound graphs w.r.t. and -Degenerate where and , then .
Proof. Let us assume that there exists a family of lower bound graphs as in the statement of the theorem. We first prove that there is a communication protocol to compute using bits of communication for , and we show later how to generalize this fact to larger . For any , let us consider . Let and . Moreover, let be the graph and, for every such that and , add a copy of the graph in Figure 5(a) to , connecting to . Define similarly. See Figure 6 for an example. We now describe a communication protocol between Alice and Bob to determine whether is 2-degenerate, and thus to compute , by simulating the peeling algorithm. This protocol is described as Algorithm 1.

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

Figure 6. Example of how Alice builds graph from the original graph and her set of vertices.
Protocol 1: Communication protocol for computing .
Alice and Bob build graphs and , respectively.
repeat
Alice peels vertices of degree at most 2 from until none exists.
Alice sends to Bob the list of identifier pairs for each gadget she peeled.
For each pair that Bob received, he removes the gadget from .
Bob peels vertices of degree at most 2 from until none exists.
Bob sends to Alice the list of identifier pairs for each gadget he peeled.
if Alice received a non-empty list then
For each pair that Alice received, she removes the gadget from .
until Alice receives an empty list
Both players determine based on whether their remaining graphs are empty.
Total communication. Each player sends 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 bits. Thus, the total number of bits exchanged between the two players is .
Correctness. Let and be the remaining graphs for Alice and Bob, respectively, that is, their computed 3-cores. First note that is in if and only if is in . 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 formed by merging and and replacing gadget pairs and by the edge . We will show that is precisely , the 3-core of .
Note that the degree of all vertices from and is the same in as in and , respectively, since each gadget contributes one to the degree of , and it was replaced by the edge . So has minimum degree at least 3 and thus . For the purpose of contradiction, let us suppose that , and let be the first vertex in peeled by Alice or Bob. Let and be the graphs and at the time when was chosen to be peeled. Suppose, w.l.o.g., that , and let us show that . For any edge , since was the first vertex in to be peeled, we know remains in the graph, that is, . If , then . If , then let us show that . First, was not peeled in line 3, since such peeling would have started by ; second, was not removed in line 9, since that would imply that is peeled by Bob in order to peel in line 6. Thus, at least 3 edges are incident to in , a contradiction. We conclude that . This shows that the 3-core is computed correctly by Alice and Bob, and thus whether is 2-degenerate. Since is a family of lower bound graphs w.r.t. and 2-Degenerate, this implies that is computed correctly.
To generalize this result to , it suffices to change the graph from Figure 5(a) to any graph with no -core but such that all vertices have degree at least , except for which has degree exactly . See Figure 5(b).
It follows from Theorem 17 that, for any , using the framework in [1], one can only obtain trivial lower bounds of rounds for -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 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 lower bounds. For simplicity, we provide lower bounds for the problem -CORE, in which each node outputs whether it is in the -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 for function 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 .
A protocol is said to run in rounds if the players exchange messages in alternating turns, with Alice starting. The deterministic communication complexity of over rounds, denoted , is the minimum of over all deterministic protocols for that run in rounds, and we define similarly for the randomized case.
Definition 19 (Pointer Chasing). The history pointer chasing problem, or , is a two-party communication complexity problem. There are two functions known by Alice and Bob, respectively. The goal is, for all , to compute , where is if is odd, and otherwise.
It is easy to solve by exchanging bits over rounds. Alice starts by sending to Bob, who then sends 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 , .
The deterministic case, which works even for 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 rounds instead.13
Since, by Theorem 18, we know it is not possible to use Theorem 17 for a non-trivial lower bound for -Core, we present a stronger version of the theorem, which considers lower bounds that include round restrictions, and which allows a graph function , instead of simply a predicate .
A graph function is a function mapping each graph to a string of bits. In the CONGEST problem of computing a graph function on network , each node has to output 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 be a function, and let be a graph function. A family of graphs with a partition , and possibly labels on the vertices and edges, is said to be a family of lower bound graphs w.r.t. and if the following properties hold:
only edges and labels in may depend on ;
only edges and labels in may depend on ;
is uniquely determined by .
Theorem 22. Fix an integer , a function , and a graph function . If there exists a family of lower bound graphs w.r.t. and , with and , then every deterministic algorithm for computing in the CONGEST model requires rounds, and every randomized algorithm requires rounds.
Proof. Let be the round complexity of a CONGEST algorithm for graph function in -node networks. Using the same simulation as for establishing Theorem 17, we obtain a communication protocol for . This protocol runs in rounds by simulating each CONGEST round with two alternating communication rounds. Moreover, it exchanges total bits as the players can only communicate bits per round per edge in the cut.
If is deterministic, then either it takes at least rounds, or it exchanges bits. In the former case, we have . In the latter, . By combining both cases, we obtain . The case of a randomized follows from the same arguments.
Using the Extended Framework
We will start by deriving lower bounds for M2CVP, and later adapting them for -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 , there exists a family of lower bound graphs w.r.t. HistPC and M2CVP, with and , such that , , with the graphs having diameter .
This proposition means that, from a pointer chasing instance, we can obtain a graph which encodes a circuit such that, for each , we can determine 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 , and , there exists a family of lower bound graphs w.r.t. HistPC and -CORE, with and , such that , , with the graphs having diameter .
Proof. For any input for HistPC, let be the graph given by Proposition 23. Then use the standard reduction from M2CVP to -CORE (see [4 §3]) to obtain . 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 from the -core of . Therefore, is a family that satisfies the statement.
Theorem 25. M2CVP on -node -diameter networks requires rounds for any randomized algorithm in the CONGEST model.
Proof. Suppose M2CVP can be solved in the CONGEST model in rounds. Consider an instance of HistPC for some that we will specify later. By Proposition 23, there exists some graph with cut , which encodes an instance of M2CVP, such that, for each , the value of can be recovered from the values of the gates of the circuit, with and .
Using Theorem 22 with , and Proposition 20, we get that
because . This is maximized when and therefore , which implies that and . Changing variables, we obtain
using the fact that when .
Theorem 26. For any , -CORE on -node -diameter networks requires 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 in the previous result is tight, in a sense, since 2-CORE can be solved in rounds on -diameter networks, as we show in § 3.4.
Remark. Theorem 26 also holds for any -approximation of the core value of each vertex. It also holds for the directed -core variant, and the -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 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. and M2CVP. At first, we consider circuits with unbounded diameter, fan-in, and fan-out. Consider an instance of . That is, we have functions . The input is given to two players, Alice and Bob, so that Alice knows , and Bob knows . To simplify notation, we take to be if is odd, and if is even. We will build a monotone circuit that can be used to compute for each .
Construction of the circuit. The circuit will have layers, where the th layer corresponds to function . Follow the description looking at the example in Figure 7. Layer has AND-gates and OR-gates , as well as OR-gates

Figure 7. Example of the circuit created when , , and , with and . Gates and wires with value 1 are bold. In particular, the output gate (marked with a ) has value 1 because .
and
Let be the set of gates in layer . Now, let be the -th (least significant) bit of in its binary representation, and let
Define similarly, but using and . The wires between gates in layer are as follows, for each :
from all gates in to ,
from to ,
from to all gates in .
Additionally, for each and , we have wires from to and from to . Finally, add a 1-gate connected to . The output of the circuit is . Alice will own
while Bob will own
Note the wires in depend only on the functions with odd indices (i.e., known by Alice), and the wires in depend only on the functions with even indices (i.e., known by Bob). The wires in are exactly those connecting to , and do not depend on any function. Furthermore, the size of the cut is . One can think of getting rid of and , connecting directly to , , or , but this would increase the size of the cut to .
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 . 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 gates and wires, and diameter .
Correctness. We can show by induction on that
evaluates to 1 if and only if ,
evaluates to 1 if and only if ,
gates in and evaluate to 1 if and only if they are in , and
gates in and evaluate to 1 if and only if they are in ).
When , (3) follows from our construction, because we added connected to and no other gates in layer 1 have inputs. For , (3) holds because of (2) for layer , and the fact that and receive inputs only from and , respectively. Now, (1) holds because of (3), and the fact that is connected to and any is connected to some gate in that evaluates to 0. Moreover, (2) holds because of (1) and the fact that is connected to all such that . Finally, (4) holds because of (2) and the connections from to .
Thus, we can correctly determine where is the only gate on that column with value 1. Hence, we have a family of lower bound graphs w.r.t. HistPC 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 -CORE we can easily create one for -DEGENERATE.14 Therefore, for the remainder of the section, we focus on algorithms for the -core problem.
For , the straightforward -round algorithm matches the lower bound of Theorem 14 up to subpolynomial factors. However, for , we provide a more efficient algorithm that runs in rounds on graphs of diameter , thus matching the known 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 . During the execution, each node of 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 broadcasts its core value estimate to its neighbors. Once receives all current estimates from its neighbors, it updates its estimate to the largest such that has at least neighbors with estimate at least . For an -node graph, after rounds, the estimates are the true core values [14 §I.A], so all nodes terminate.
Remark. Even on -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 . Indeed, for the graph consisting of an -node path plus a universal node, the algorithm takes rounds to stabilize. In fact, at the end of round , every node at distance at most from the endpoints of the -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 , every node sets its core value estimate to its true core value, which is 2.
We now present a more efficient CONGEST algorithm when .
Theorem 27. 2-Core can be solved in rounds in the CONGEST model on -node networks of diameter .
Proof. Let be a graph of diameter . The first phase of our algorithm starts with the execution of the standard procedure for selecting as leader a node of and computing a breadth-first search tree of rooted at . This takes rounds in the CONGEST model (see [30 §5.5-5.6] for details). The execution of this procedure determines, for each node of , its distance to the root , a pointer p[] to its parent, and the collection of identifiers of ’s children in . In the next phases, each node uses two additional Boolean variables, up[] and down[], to identify 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 incident to a non-tree edge sets variable up[] to true conveying that it belongs to a cycle in . Afterward, every leaf of upcasts up[] to its parent. When an internal node of has seen all messages being upcast by its children, it sets up[] to true if it received at least one true value. The second phase finishes when the root of has processed all its children’s messages. Besides this, in preparation for the third phase, during the upcast phase, sets down[] to true if it received at least two true values from its children.
During the third (downcast) phase, messages are propagated downward through starting from the root , which broadcasts down[]. When a node receives the message from its parent, it sets down[] to true if the message is true, and then it propagates down[] to its children. See Figure 8 for an example.

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 indicate its final state: a blue upward arrow for and a purple downward arrow for . 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 claims that it belongs to the 2-core of if and only if both up[] and down[] equal true at the end of the downcast phase.
By construction, our algorithm completes in rounds in CONGEST, since building the breadth-first search tree and both the upcast and downcast phases take rounds, as the tree has depth .
The following lemmas refer to the values of up and down at the end of the execution of the algorithm. We denote by the subtree of rooted at .
Lemma 28. up[] = true if and only if a node in is in the 2-core of .
Proof. If , then there is a descendant (in ) of incident to a non-tree edge. This descendant, which is a node of , is in a cycle in , and thus is in the 2-core of . On the other hand, if is in the 2-core of , then let be a descendant of in the 2-core with maximum depth in . Each of the at least two edges in the 2-core incident to does not go to a descendant of . Therefore, at least one of these edges is not in , and hence . ◇
Lemma 29. if and only if is in the 2-core of .
Proof. The proof is by induction on the depth of in . First, assume . If and , then because , and, by induction, is in the 2-core of . By Lemma 28, there is also a path in from to a node in the 2-core. So, there are two edge-disjoint paths from to vertices in the 2-core, which implies that is also in the 2-core. If or , then, as , must have two children and such that . By Lemma 28, there are two edge-disjoint paths from to vertices in the 2-core. So, is in the 2-core of .
Now, assume is in the 2-core of . By Lemma 28, . If and is in the 2-core, then, by induction, , and hence . If or is not in the 2-core, then no non-tree edge is incident to , because in a BFS tree the fundamental cycle of a non-tree edge always includes . There are at least two edges and in the 2-core, and and must be distinct children of , since is not in the 2-core. By Lemma 28, , thus . ◇
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 rounds), 3-Core (and 2-Degenerate) cannot (i.e., they need 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 , solving -Degenerate requires rounds, even with a randomized algorithm, and even for -approximation. Furthermore, we provided conditional lower bounds suggesting that the problem is likely even harder. Specifically, we showed that algorithms running in 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 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]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]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]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]Anderson, R., Mayr, E.W.: A P-complete problem and approximations to it. Tech. rep., Stanford University (1984)
- [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]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]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]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]Barenboim, L., Elkin, M.: Distributed graph coloring: Fundamentals and recent developments (2013)DOI
- [10]Batagelj, V., Zaversnik, M.: An O(m) algorithm for cores decomposition of networks (2003), http://arxiv.org/abs/cs/0310049
- [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]Bondy, J., Murty, U.: Graph Theory. Springer (2008)
- [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]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]Condon, A.: A theory of strict P-completeness. Computational Complexity 4(3), 220–241 (1994)
- [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]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]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]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]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]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]Parallel and streaming algorithms for k-core decompositionarxiv.org/abs/1808.02546
- [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]Ghaffari, M., Lymouri, C.: Simple and near-optimal distributed coloring for sparse graphs. arXiv:1708.06275 (2017)arxiv.org/abs/1708.06275
- [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]Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, New York (1995)DOI
- [27]Guo, B., Zhao, R.: Experimental evaluation of distributed k-core decomposition (2025)arxiv.org/abs/2406.17580
- [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]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]Hirvonen, J., Suomela, J.: Distributed Algorithms (2020). https://jukkasuomela.fi/da2020/da2020.pdf
- [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]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]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]Kruskal, C.P., Rudolph, L., Snir, M.: A complexity theory of efficient parallel algorithms. Theoretical Computer Science 71(1), 95–132 (1990)
- [35]Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms 28(1), 40–66 (1998)
- [36]Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)DOI
- [37]Mak, L.: Parallelism always helps. SIAM J. Comput. 26(1), 153–172 (1997)DOI
- [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]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]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]Mittal, P.: How to Color Graphs, and How Not to Chase Pointers. Ph.D. thesis, University of Waterloo (May 2026)
- [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]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]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]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]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]O’Brien, M.P., Sullivan, B.D.: Locally estimating core numbers. In: IEEE Int. Conf. on Data Mining. pp. 460–469 (2014)
- [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]Rao, A., Yehudayoff, A.: Communication complexity: and applications. Cambridge University Press (2020)
- [50]Seidman, S.B.: Network structure and minimum degree. Social Networks 5(3), 269–287 (1983)DOI
- [51]Williams, R.: Parallelizing time with polynomial circuits. Theory of Computing Systems 48(1), 150–169 (2011)
- [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



