We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires @math rounds in the worst case in the CONGEST model, as well as any algorithm for @math -coloring a graph, where @math is the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple @math lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a complexity of @math . We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.
Distance computation problems have been widely studied in the CONGEST model for both weighted and unweighted networks @cite_49 @cite_32 @cite_59 @cite_63 @cite_37 @cite_4 @cite_41 @cite_60 @cite_24 @cite_34 @cite_58 . One of the most fundamental problems of distance computations is computing all pairs shortest paths. For unweighted networks, an upper bound of @math was recently shown by @cite_34 , matching the lower bound of @cite_32 . Moreover, the possibility of bypassing this near-linear barrier for any constant approximation factor was ruled out by @cite_24 . For the weighted case, however, we are still very far from understanding the complexity of APSP, as there is still a huge gap between the upper and lower bounds. Recently, Elkin @cite_47 showed an @math upper bound for weighted APSP, while the previously highest lower bound was the near-linear lower bound of @cite_24 (which holds also for any @math -approximation factor in the weighted case).
@cite_37 @cite_4 @cite_60 @cite_41 @cite_58 @cite_32 @cite_24 @cite_63 @cite_59 @cite_49 @cite_47 @cite_34
1515635142 2107282727 2949588463 1582638066 2040011014 2397361776 2048098617 2399682168 2952103668 2474966478
We study the broadcast version of the CONGEST CLIQUE model of distributed computing. In this model, in each round, any node in a network of size @math can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized @math -approximation algorithm to compute all pairs shortest paths (APSP) in time @math on weighted graphs, where we use the convention that @math is essentially @math polylog @math and @math is essentially @math polylog @math . We complement this result by proving that any randomized @math -approximation of APSP and @math -approximation of the diameter of a graph takes @math time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a @math -approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST CLIQUE model and contrasts a recent @math -approximation for APSP that runs in time @math in the unicast version of the CONGEST CLIQUE model. On the positive side we provide a deterministic version of Nanongkai's @math -approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model presented by Lenzen and Peleg at PODC'13. Given a simple graph G=(V,E) and a set of sources S ⊆ V, denote for each node ν e V by Lν(∞) the lexicographically ordered list of distance source pairs (d(s,v),s), where s ∈ S. For integers d,k ∈ N∪ ∞ , we consider the source detection, or (S,d,k)-detection task, requiring each node v to learn the first k entries of Lν(∞) (if for all of them d(s,v) ≤ d) or all entries (d(s,v),s) ∈ Lν(∞) satisfying that d(s,v) ≤ d (otherwise). Solutions to this problem provide natural generalizations of concurrent breadth-first search (BFS) tree constructions. For example, the special case of k=∞ requires each source s ∈ S to build a complete BFS tree rooted at s, whereas the special case of d=∞ and S=V requires constructing a partial BFS tree comprising at least k nodes from every node in V. In this work, we give a simple, near-optimal solution for the source detection task in the CONGEST model, where messages contain at most O(log n) bits, running in d+k rounds. We demonstrate its utility for various routing problems, exact and approximate diameter computation, and spanner construction. For those problems, we obtain algorithms in the CONGEST model that are faster and in some cases much simpler than previous solutions. We study approximate distributed solutions to the weighted all-pairs-shortest-paths (APSP) problem in the CONGEST model. We obtain the following results. @math A deterministic @math -approximation to APSP in @math rounds. This improves over the best previously known algorithm, by both derandomizing it and by reducing the running time by a @math factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and require that these names are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of @math . In the relabeling model, we obtain the following results. @math A randomized @math -approximation to APSP, for any integer @math , running in @math rounds, where @math is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from @math to @math . Also, the new algorithm uses uses labels of asymptotically optimal size, namely @math bits. @math A randomized @math -approximation to APSP, for any integer @math , running in time @math and producing compact routing tables of size @math . The node lables consist of @math bits. This improves on the approximation ratio of @math for tables of that size achieved by the best previously known algorithm, which terminates faster, in @math rounds. We study the problem of computing the diameter of a network in a distributed way. The model of distributed computation we consider is: in each synchronous round, each node can transmit a different (but short) message to each of its neighbors. We provide an Ω(n) lower bound for the number of communication rounds needed, where n denotes the number of nodes in the network. This lower bound is valid even if the diameter of the network is a small constant. We also show that a (3 2 − e)-approximation of the diameter requires Ω (√n + D) rounds. Furthermore we use our new technique to prove an Ω (√n + D) lower bound on approximating the girth of a graph by a factor 2 − e. A distributed network is modeled by a graph having n nodes (processors) and diameter D. We study the time complexity of approximating weighted (undirected) shortest paths on distributed networks with a O (log n) bandwidth restriction on edges (the standard synchronous CONGEST model). The question whether approximation algorithms help speed up the shortest paths and distance computation (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted case of this problem is well-understood while its weighted counterpart is fundamental problem in the area of distributed approximation algorithms and remains widely open. We present new algorithms for computing both single-source shortest paths (SSSP) and all-pairs shortest paths (APSP) in the weighted case. Our main result is an algorithm for SSSP. Previous results are the classic O(n)-time Bellman-Ford algorithm and an O(n1 2+1 2k + D)-time (8k⌈log(k + 1)⌉ --1)-approximation algorithm, for any integer k ≥ 1, which follows from the result of Lenzen and Patt-Shamir (STOC 2013). (Note that Lenzen and Patt-Shamir in fact solve a harder problem, and we use O(·) to hide the O(poly log n) term.) We present an O (n1 2D1 4 + D)-time (1 + o(1))-approximation algorithm for SSSP. This algorithm is sublinear-time as long as D is sublinear, thus yielding a sublinear-time algorithm with almost optimal solution. When D is small, our running time matches the lower bound of Ω(n1 2 + D) by Das (SICOMP 2012), which holds even when D=Θ(log n), up to a poly log n factor. As a by-product of our technique, we obtain a simple O (n)-time (1+ o(1))-approximation algorithm for APSP, improving the previous O(n)-time O(1)-approximation algorithm following from the results of Lenzen and Patt-Shamir. We also prove a matching lower bound. Our techniques also yield an O(n1 2) time algorithm on fully-connected networks, which guarantees an exact solution for SSSP and a (2+ o(1))-approximate solution for APSP. All our algorithms rely on two new simple tools: light-weight algorithm for bounded-hop SSSP and shortest-path diameter reduction via shortcuts. These tools might be of an independent interest and useful in designing other distributed algorithms. We present an algorithm to compute All Pairs Shortest Paths (APSP) of a network in a distributed way. The model of distributed computation we consider is the message passing model: in each synchronous round, every node can transmit a different (but short) message to each of its neighbors. We provide an algorithm that computes APSP in O(n) communication rounds, where n denotes the number of nodes in the network. This implies a linear time algorithm for computing the diameter of a network. Due to a lower bound these two algorithms are optimal up to a logarithmic factor. Furthermore, we present a new lower bound for approximating the diameter D of a graph: Being allowed to answer D+1 or D can speed up the computation by at most a factor D. On the positive side, we provide an algorithm that achieves such a speedup of D and computes an (1+eepsilon) multiplicative approximation of the diameter. We extend these algorithms to compute or approximate other problems, such as girth, radius, center and peripheral vertices. At the heart of these approximation algorithms is the S-Shortest Paths problem which we solve in O(|S|+D) time. We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Specifically, we show an @math lower bound for computing the diameter in sparse networks, which was previously known only for dense networks [, SODA 2012]. In fact, we can even modify our construction to obtain graphs with constant degree, using a simple but powerful degree-reduction technique which we define. Moreover, our technique allows us to show @math lower bounds for computing @math -approximations of the diameter or the radius, and for computing a @math -approximation of all eccentricities. For radius, we are unaware of any previous lower bounds. For diameter, these greatly improve upon previous lower bounds and are tight up to polylogarithmic factors [, SODA 2012], and for eccentricities the improvement is both in the lower bound and in the approximation factor [Holzer and Wattenhofer, PODC 2012]. Interestingly, our technique also allows showing an almost-linear lower bound for the verification of @math -spanners, for @math . The distributed single-source shortest paths problem is one of the most fundamental and central problems in the message-passing distributed computing. Classical Bellman-Ford algorithm solves it in @math time, where @math is the number of vertices in the input graph @math . Peleg and Rubinovich (FOCS'99) showed a lower bound of @math for this problem, where @math is the hop-diameter of @math . Whether or not this problem can be solved in @math time when @math is relatively small is a major notorious open question. Despite intensive research LP13,N14,HKN15,EN16,BKKL16 that yielded near-optimal algorithms for the approximate variant of this problem, no progress was reported for the original problem. In this paper we answer this question in the affirmative. We devise an algorithm that requires @math time, for @math , and @math time, for larger @math . This running time is sublinear in @math in almost the entire range of parameters, specifically, for @math . For the all-pairs shortest paths problem, our algorithm requires @math time, regardless of the value of @math . We also devise the first algorithm with non-trivial complexity guarantees for computing exact shortest paths in the multipass semi-streaming model of computation. From the technical viewpoint, our algorithm computes a hopset @math of a skeleton graph @math of @math without first computing @math itself. We then conduct a Bellman-Ford exploration in @math , while computing the required edges of @math on the fly. As a result, our algorithm computes exactly those edges of @math that it really needs, rather than computing approximately the entire @math . Given an unweighted and undirected graph, this paper aims to give a tight distributed algorithm for computing the all pairs shortest paths (APSP) under synchronous communications and the CONGEST(B) model, where each node can only transfer B bits of information along each incident edge in a round. The best previous results for distributively computing APSP need O(N+D) time where N is the number of nodes and D is the diameter [1,2]. However, there is still a B factor gap from the lower bound Ω(N B+D) [1]. In order to close this gap, we propose a multiplexing technique to push the parallelization of distributed BFS tree constructions to the limit such that we can solve APSP in O(N B+D) time which meets the lower bound. This result also implies a Θ(N B+D) time distributed algorithm for diameter. In addition, we extend our distributed algorithm to compute girth which is the length of the shortest cycle and clustering coefficient (CC) which is related to counting the number of triangles incident to each node. The time complexities for computing these two graph properties are also O(N B+D).