In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we significantly improve upon the state of the art in the deterministic Congested Clique. In particular, we obtain the following four results on undirected graphs:

Abstract In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed Congested Clique model. Specifically, we show the following results for undirected n -node graphs. For every integer $$k \ge 1$$ , O (1)-round algorithms for constructing O ( k )-spanners with $$O(n^{1+1/k})$$ edges in unweighted graphs, and O ( k )-spanners with $$O(n^{1+1/k} \log {n})$$ edges in weighted graphs. An O (1)-round algorithm for $$O(\log {n})$$ -approximation for APSP in unweighted graphs. An O (1)-round algorithm for $$O(\log ^2{n})$$ -approximation for APSP in weighted graphs. All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O ( k )-spanners in this model require $${{\,\textrm{poly}\,}}(\log {k})$$ rounds [Parter, Yogev, DISC ’18] [Biswas, Dory, Ghaffari, Mitrovic, Nazari, SPAA ’21], and the fastest algorithms for approximate shortest paths require $${{\,\textrm{poly}\,}}(\log {\log {n}})$$ rounds [Dory, Parter, PODC ’20]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O (1)-round algorithms for spanners and approximate shortest paths in this model as well.

Abstract. The paper presents fault-tolerant (FT) labeling schemes for general graphs, as well as improved FT routing schemes. For a given [Formula: see text]-vertex graph [Formula: see text] and a bound [Formula: see text] on the number of faults, an [Formula: see text]-FT connectivity labeling scheme is a distributed data structure that assigns to each of the graph edges and vertices a short label, such that given the labels of a vertex pair [Formula: see text] and [Formula: see text], and the labels of at most [Formula: see text] failing edges [Formula: see text], one can determine if [Formula: see text] and [Formula: see text] are connected in [Formula: see text]. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS ’07], compact FT labeling schemes have been devised only for a limited collection of graph families. In this work, we fill in this gap by proposing two (independent) FT connectivity labeling schemes for general graphs, with a nearly optimal label length. This serves the basis for providing also FT approximate distance labeling schemes, and ultimately also routing schemes. Our main results for an [Formula: see text]-vertex graph and a fault bound [Formula: see text] are (1) There is a randomized FT connectivity labeling scheme with a label length of [Formula: see text] bits, hence optimal for [Formula: see text]. This scheme is based on the notion of cycle space sampling [Pritchard, Thurimella, TALG ’11]. (2) There is a randomized FT connectivity labeling scheme with a label length of [Formula: see text] bits (independent of the number of faults [Formula: see text]). This scheme is based on the notion of linear sketches of [Ahn et al., SODA ’12]. (3) For a given stretch parameter [Formula: see text], there is a randomized routing scheme that routes a message from [Formula: see text] to [Formula: see text] in the presence of a set [Formula: see text] of faulty edges (unknown to [Formula: see text]) over a path of length [Formula: see text]. The routing labels have [Formula: see text] bits, the header size is [Formula: see text] bits, and each routing table has only [Formula: see text] bits. (Throughout the paper, we use the notation [Formula: see text] to hide poly-logarithmic in [Formula: see text] terms.) The results also hold for weighted graphs with positive polynomial weights. This significantly improves over the state-of-the-art bounds by [Chechik, ICALP ’11], providing the first scheme with sublinear FT labeling and routing schemes for general graphs.

The dual of a planar graph G is a planar graph G* that has a vertex for each face of G and an edge for each pair of adjacent faces of G. The profound relationship between a planar graph and its dual has been the algorithmic basis for solving numerous (centralized) classical problems on planar graphs involving distances, flows, and cuts. In the distributed setting however, the only use of planar duality is for finding a recursive decomposition of G [DISC 2017, STOC 2019].

Abstract We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take $$\textrm{poly}(\log {\log {n}})$$ poly ( log log n ) rounds in the near-linear memory MPC model. Our results are for unweighted undirected graphs with n vertices and m edges. Our first contribution is a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation algorithm for Single-Source Shortest Paths (SSSP) that takes $$\textrm{poly}(\log {\log {n}})$$ poly ( log log n ) rounds in the near-linear MPC model, where the memory per machine is $$\tilde{O}(n)$$ O ~ ( n ) and the total memory is $$\tilde{O}(mn^{\rho })$$ O ~ ( m n ρ ) , where $$\rho $$ ρ is a small constant. Our second contribution is a distance oracle that allows to approximate the distance between any pair of vertices. The distance oracle is constructed in $$\textrm{poly}(\log {\log {n}})$$ poly ( log log n ) rounds and allows to query a $$(1+\epsilon )(2k-1)$$ ( 1 + ϵ ) ( 2 k - 1 ) -approximate distance between any pair of vertices u and v in O(1) additional rounds. The algorithm is for the near-linear memory MPC model with total memory of size $$\tilde{O}((m+n^{1+\rho })n^{1/k})$$ O ~ ( ( m + n 1 + ρ ) n 1 / k ) , where $$\rho $$ ρ is a small constant. While our algorithms are for the near-linear MPC model, in fact they only use one machine with $$\tilde{O}(n)$$ O ~ ( n ) memory, where the rest of machines can have sublinear memory of size $$O(n^{\gamma })$$ O ( n γ ) for a small constant $$\gamma < 1$$ γ < 1

We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with m edges and n nodes undergoing edge deletions, we provide four new approximate decremental APSP algorithms, two for weighted and two for unweighted graphs. Our first result is (2 + ϵ)-APSP with total update time Õ(m1/2n3/2) (when m = n1+c for any constant 0 < c < 1). Prior to our work the fastest algorithm for weighted graphs with approximation at most 3 had total Õ(mn) update time for (1 + ϵ)-APSP [Bernstein, SICOMP 2016]. Our second result is (2 + ϵ, Wu,v)-APSP with total update time Õ(nm3/4), where the second term is an additive stretch with respect to Wu,v, the maximum weight on the shortest path from u to v. Our third result is (2 + ϵ)-APSP for unweighted graphs in Õ(m7/4) update time, which for sparse graphs (m = o(n8/7)) is the first subquadratic (2 + ϵ)-approximation. Our last result for unweighted graphs is (1 + ϵ, 2(k − 1))-APSP, for k ≥ 2, with Õ(n2−1/km1/k) total update time (when m = n1+c for any constant c > 0). For comparison, in the special case of (1 + ϵ, 2)-approximation, this improves over the state-of-the-art algorithm by [Henzinger, Krinninger, Nanongkai, SICOMP 2016] with total update time of Õ(n2.5). All of our results are randomized, work against an oblivious adversary, and have constant query time.

In this paper, we present new algorithms for approximating All-Pairs Shortest Paths (APSP) in the Congested Clique model. We present randomized algorithms for weighted undirected graphs.

In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for 2-approximate APSP in Õ(n2.5-r + nω(r)) time, for any r ∈ [0,1]. This is O(n2.032) time, using known bounds for rectangular matrix multiplication nω(r) [Le Gall, Urrutia, SODA 2018]. Our result improves on the Õ(n2·25) bound of [Roditty, STOC 2023], and on the bound of [Baswana, Kavitha, SICOMP 2010] for graphs with m ≥ n1·532 edges.

We revisit the classic broadcast problem, wherein we have k messages, each composed of O(log n) bits, distributed arbitrarily across a network. The objective is to broadcast these messages to all nodes in the network. In the distributed CONGEST model, a textbook algorithm solves this problem in O(D+k) rounds, where D is the diameter of the graph. While the O(D) term in the round complexity is unavoidable---given that Ω(D) rounds are necessary to solve broadcast in any graph ---it remains unclear whether the O(k) term is needed in all graphs. In cases where the minimum cut size is one, simply transmitting messages from one side of the cut to the other would require Ω(k) rounds. However, if the size of the minimum cut is larger, it may be possible to develop faster algorithms. This motivates the exploration of the broadcast problem in networks with high edge connectivity.

We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take poly(łogłogn ) rounds in the near-linear memory MPC model. Our results are for unweighted undirected graphs with n vertices and m edges.

Abstract We describe a simple deterministic $$O( \varepsilon ^{-1} \log \Delta )$$ O ( ε - 1 log Δ ) round distributed algorithm for $$(2\alpha +1)(1 + \varepsilon )$$ ( 2 α + 1 ) ( 1 + ε ) approximation of minimum weighted dominating set on graphs with arboricity at most $$\alpha $$ α . Here $$\Delta $$ Δ denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized $$O(\alpha ^2)$$ O ( α 2 ) approximation in $$O(\log n)$$ O ( log n ) rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic $$O(\alpha \log \Delta )$$ O ( α log Δ ) approximation in $$O(\log \Delta )$$ O ( log Δ ) rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic $$O(\alpha )$$ O ( α ) approximation in $$O(\log ^2 \Delta )$$ O ( log 2 Δ ) rounds (implicit in Bansal et al. in Inform Process Lett 122:21–24, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized $$O(\alpha )$$ O ( α ) approximation in $$O(\alpha \log n)$$ O ( α log n ) rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized $$O(\alpha \log \Delta )$$ O ( α log Δ ) round distributed algorithm that sharpens the approximation factor to $$\alpha (1+o(1))$$ α ( 1 + o ( 1 ) ) . If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve $$\alpha - 1 - \varepsilon $$ α - 1 - ε approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017).

The minimum-cost k-edge-connected spanning subgraph (k-ECSS) problem is a generalization and strengthening of the well-studied minimum-cost spanning tree (MST) problem. While the round complexity of distributedly computing the latter has been well-understood, the former remains mostly open, especially as soon as k ≥ 3. In this paper, we present the first distributed algorithm that computes an approximation of k-ECSS in sublinear time for general k. Concretely, we describe a randomized distributed algorithm that, in rounds, computes a k-edge-connected spanning subgraph whose cost is within an O(log n log k) factor of optimal. Here, n and D denote the number of vertices and diameter of the graph, respectively. This time complexity is nearly optimal for any k = poly(log n), almost matching an lower bound. Our algorithm is the first to achieve a sublinear round complexity for k ≥ 3. We note that this case is considerably more challenging than the well-studied and well-understood k =1 case—better known as MST—and the closely related k = 2 case. Our algorithm is based on reducing the k-ECSS problem to k set cover instances, in which we gradually augment the connectivity of the spanning subgraph. To solve each set cover instance, we combine new structural observations on minimum cuts with graph sketching ideas. One key ingredient in our algorithm is a novel structural lemma that allows us to compress the information about all minimum cuts in a graph into a succinct representation, which is computed in a decentralized fashion. We hope that this succinct representation may find applications in other computational settings or for other problems.

We describe a simple deterministic O(ε-1 log Δ) round distributed algorithm for (2α+ 1) (1 + ε) approximation of minimum weighted dominating set on graphs with arboricity at most α. Here Δ denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation [Kuhn, Moscibroda, and Wattenhofer JACM'16].

We present improved deterministic algorithms for approximating shortest paths in the Congested Clique model of distributed computing. We obtain poly(log log n )-round algorithms for the following problems in unweighted undirected n -vertex graphs: ( 1 + ϵ )-approximation of multi-source shortest paths (MSSP) from O (√ n ) sources. (2 + ϵ )-approximation of all pairs shortest paths (APSP). (1 + ϵ , β)-approximation of APSP where β = O (log log n / ϵ ) log log n . These bounds improve exponentially over the state-of-the-art poly-logarithmic bounds due to [Censor-Hillel et al., PODC19]. It also provides the first nearly-additive bounds for the APSP problem in sub-polynomial time. Our approach is based on distinguishing between short and long distances based on some distance threshold t = O ( β / ϵ ) where β = O (log log n / ϵ ) log log n . Handling the long distances is done by devising a new algorithm for computing a sparse (1 + ϵ , β ) emulator with O ( n log log n ) edges. For the short distances, we provide distance-sensitive variants for the distance tool-kit of [Censor-Hillel et al., PODC19]. By exploiting the fact that this tool-kit should be applied only on local balls of radius t , their round complexities get improved from poly (log n ) to poly (log t ). Finally, our deterministic solutions for these problems are based on a derandomization scheme of a novel variant of the hitting set problem, which might be of independent interest.

In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed CONGESTED CLIQUE model. Specifically, we show the following results for undirected n-node graphs. ulFor every integer k ≥ 1, O(1)-round algorithms for constructing O(k)-spanners with O(n1+1/k) edges in unweighted graphs, and O(k)-spanners with O(n1+1/k log n) edges in weighted graphs. An O(1)-round algorithm for O(log n)-approximation for APSP in unweighted graphs. An O(1)-round algorithm for O(log2n)-approximation for APSP in weighted graphs. All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O(k)-spanners in this model require poly(log k) rounds [Parter, Yogev, DISC '18] [Biswas et al., SPAA '21], and the fastest algorithms for approximate shortest paths require poly(log log n) rounds [Dory, Parter, PODC '20]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O(1)-round algorithms for spanners and approximate shortest paths in this model as well.

Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms---usually sublogarithmic-time and often poly(łogłog n)-time, or even faster---for a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widely-adopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an all-to-all manner to process large-scale data. Contributing to this line of work on MPC graph algorithms, we present poly(łog k) ε poly(łogłog n) round MPC algorithms for computing O(k^1+o(1) )-spanners in the strongly sublinear regime of local memory. To the best of our knowledge, these are the first sublogarithmic-time MPC algorithms for spanner construction.

Minimum-weight cut (min-cut) is a basic measure of a network’s connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC’96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]) can guarantee a solution that is (1+є)-approximation at best while the exact Õ(n0.8D0.2 + n0.9)-time algorithm [Ghaffari, Nowicki, Thorup, SODA’20] works only on simple networks (no weights and no parallel edges). Throughout, n and D denote the network’s number of vertices and hop-diameter, respectively. For the weighted case, the best bound was Õ(n) [Daga, Henzinger, Nanongkai, Saranurak, STOC’19]. In this paper, we provide an exact Õ(√n + D)-time algorithm for computing min-cut on weighted networks. Our result improves even the previous algorithm that works only on simple networks. Its time complexity matches the known lower bound up to polylogarithmic factors. At the heart of our algorithm are a routing trick and two structural lemmas regarding the structure of a minimum cut of a graph. These two structural lemmas considerably strengthen and generalize the framework of Mukhopadhyay-Nanongkai [STOC’20] and can be of independent interest.

Abstract We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include: A $$(2+\epsilon )$$ ( 2 + ϵ ) -approximation for all-pairs shortest paths in $$O(\log ^2{n} / \epsilon )$$ O ( log 2 n / ϵ ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model. A $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation for multi-source shortest paths from $$O(\sqrt{n})$$ O ( n ) sources in $$O(\log ^2{n} / \epsilon )$$ O ( log 2 n / ϵ ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size. Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in $$\tilde{O}(n^{1/6})$$ O ~ ( n 1 / 6 ) rounds.

We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and hardness results. Our main hardness result shows that an $\alpha$-approximation for the minimum directed $k$-spanner problem for $k \geq 5$ requires $\Omega(n /\sqrt{\alpha}\log{n})$ rounds using deterministic algorithms or $\Omega(\sqrt{n }/\sqrt{\alpha}\log{n})$ rounds using randomized ones, in the Congest model of distributed computing. Combined with the constant-round $O(n^{\epsilon})$-approximation algorithm in the Local model of [L. Barenboim, M. Elkin, and C. Gavoille, Theoret. Comput. Sci., 751 (2016), pp. 2--23], as well as a polylog-round $(1+\epsilon)$-approximation algorithm in the Local model that we show here, our lower bounds for the Congest model imply a strict separation between the Local and Congest models. Notably, to the best of our knowledge, this is the first separation between these models for a local approximation problem. Similarly, a separation between the directed and undirected cases is implied. We also prove hardness results for weighted $k$-spanners and for unweighted undirected $k$-spanners for $k \geq 4$ in the Congest model. In addition, we show lower bounds for the minimum weighted 2-spanner problem in the Congest and Local models. On the algorithmic side, apart from the aforementioned $(1+\epsilon)$-approximation algorithm for minimum $k$-spanners, our main contribution is a new distributed construction of minimum 2-spanners that uses only polynomial local computations. Our algorithm has a guaranteed approximation ratio of $O(\log(m/n))$ for a graph with $n$ vertices and $m$ edges, which matches the best known ratio for polynomial-time sequential algorithms [G. Kortsarz and D. Peleg, J. Algorithms, 17 (1994), pp. 222--236], and is tight if we restrict ourselves to polynomial local computations. An algorithm with this approximation factor was not previously known for the distributed setting. The number of rounds required for our algorithm is $O(\log{n}\log{\Delta})$ with high probability, where $\Delta$ is the maximum degree in the graph. Our approach allows us to extend our algorithm to work also for the directed, weighted, and client-server variants of the problem. It also provides a Congest algorithm for the minimum dominating set problem, with a guaranteed $O(\log{\Delta})$ approximation ratio.

We present improved deterministic algorithms for approximating shortest paths in the Congested Cliqe model of distributed computing. We obtain poly(log log n)-round algorithms for the following problems in unweighted undirected n-vertex graphs:

The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G , such that \(T \cup Aug\) is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JáJá (SIAM J Comput 10(2):270–283, 1981 ). Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov (ACM Trans Algorithms 12(2):23, 2016 ). Recent breakthroughs give an approximation of 1.458 for unweighted TAP (Grandoni et al. in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing (STOC 2018), 2018 ), and approximations better than 2 for bounded weights (Adjiashvili in: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms (SODA), 2017 ; Fiorini et al. in: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms (SODA 2018), New Orleans, LA, USA, 2018 . https://doi.org/10.1137/1.9781611975031.53 ). In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O ( h ) rounds, where h is the height of T . When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in \(O(D+\sqrt{n}\log ^*{n})\) rounds, where n is the number of vertices and D is the diameter of G . Immediate consequences of our results are an O ( D )-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an \(O(h_{MST}+\sqrt{n}\log ^{*}{n})\) -round 3-approximation algorithm for the weighted case, where \(h_{MST}\) is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2. Finally, we complement our study with proving lower bounds for distributed approximations of TAP.

This paper studies lower bounds for fundamental optimization problems in the CONGEST model. We show that solving problems exactly in this model can be a hard task, by providing tildeΩmega (n2) lower bounds for cornerstone problems, such as minimum dominating set (MDS), Hamiltonian path, Steiner tree and max-cut. These are almost tight, since all of these problems can be solved optimally in O(n2) rounds. Moreover, we show that even in bounded-degree graphs and even in simple graphs with maximum degree 5 and logarithmic diameter, it holds that various tasks, such as finding a maximum independent set (MaxIS) or a minimum vertex cover, are still difficult, requiring a near-tight number of tildeΩ (n) rounds.

The minimum-weight 2-edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of the well-studied minimum-weight spanning tree (MST) problem, and it has received considerable attention in the area of network design. The latter problem asks for a minimum-weight subgraph with an edge connectivity of 1 between each pair of vertices while the former strengthens this edge-connectivity requirement to 2. Despite this resemblance, the 2-ECSS problem is considerably more complex than MST. While MST admits a linear-time centralized exact algorithm, 2-ECSS is NP-hard and the best known centralized approximation algorithm for it (that runs in polynomial time) gives a 2-approximation.

In the minimum k-edge-connected spanning subgraph (k-ECSS) problem the goal is to find the minimum weight subgraph resistant to up to k-1 edge failures. This is a central problem in network design, and a natural generalization of the minimum spanning tree (MST) problem. While the MST problem has been studied extensively by the distributed computing community, for k ≥2 less is known in the distributed setting.

A minimum spanning tree (MST) is an essential structure for distributed algorithms, since it is a low-cost connected subgraph which provides an efficient way to communicate in a network. However, trees cannot survive even one link failure. In this paper, we study the Tree Augmentation Problem (TAP), for which the input is a graph G and a spanning tree T of G and the goal is to augment T with a minimum (or minimum weight) set of edges Aug from G, such that T ∪ Aug remains connected after a failure of any single link.