The reachability diameter (ReachDiam) of a directed graph is the maximum distance over all pairs u,v where v is reachable from u. This notion is present in the definition of shortcut sets, and the name was recently coined in that context by Haeupler, Jiang, and Saranurak [SOSA 2026]. While this is a very natural notion of diameter in directed graphs, and especially DAGs, it is so far not computationally explored. Other definitions of diameter in directed graphs are either trivial (infinite) in graphs that are not strongly connected (e.g., the classical definition) or are non-trivial only in highly restrictive graph classes (e.g., Min-Diameter). We initiate the problem of computing the (approximate) reachability diameter from a fine-grained complexity point of view. Under certain fine-grained assumptions, we prove that there is no algorithm in time 𝒪(n^{ω - ε}) that gives any approximation of ReachDiam in weighted graphs. Similarly, there is no algorithm with better than 2-approximation for unweighted graphs in this time. To supplement this, we provide algorithmic upper bounds that lead to additive approximation of ReachDiam for unweighted graphs. Hence, we establish a strong separation between the weighted and unweighted cases, which makes this type of diameter different in nature than other known notions. Considering the hardness in general weighted graphs, we also study special graph classes and get small constant approximations for DAGs with bounded width or graphs with bounded treewidth. Interestingly, our techniques also lead to exact hopsets with hopbound 2 for bounded treewidth graphs. This and some of our upper bounds for general graphs show technical connections between approximating ReachDiam and computing shortcut sets and hopsets.

For a given graph G, a hopset H with hopbound β and stretch α is a set of edges such that between every pair of vertices u and v, there is a path with at most β hops in G ∪ H that approximates the distance between u and v up to a multiplicative stretch of α. Hopsets have found a wide range of applications for distance-based problems in various computational models since the 90s. More recently, there has been significant interest in understanding these fundamental objects from an existential and structural perspective. But all of this work takes a worst-case (or existential) point of view: How many edges do we need to add to satisfy a given hopbound and stretch requirement for any input graph? We initiate the study of the natural optimization variant of this problem: given a specific graph instance, what is the minimum number of edges that satisfy the hopbound and stretch requirements? We give approximation algorithms for a generalized hopset problem which, when combined with known existential bounds, lead to different approximation guarantees for various regimes depending on hopbound, stretch, and directed vs. undirected inputs. We complement our upper bounds with a lower bound that implies Label Cover hardness for directed hopsets and shortcut sets with hopbound at least 3.

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.

Dynamic algorithms operate on inputs undergoing updates, e.g., insertions or deletions of edges or vertices. After processing each update, the algorithm has to answer queries regarding the current state of the input data. We study dynamic algorithms in the model of algorithms with predictions (also known as learning-augmented algorithms). We assume the algorithm is given imperfect predictions regarding future updates, and we ask how such predictions can be used to improve the running time. In other words, we study the complexity of dynamic problems parameterized by the prediction accuracy. This can be seen as a model interpolating between classic online dynamic algorithms - which know nothing about future updates - and offline dynamic algorithms with the whole update sequence known upfront, which is similar to having perfect predictions. Our results give smooth tradeoffs between these two extreme settings.

In this paper we give the first efficient algorithms for the k-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into k sets by choosing k centers such that the maximum distance from any data point to its closest center is minimized. It is known that it is NP-hard to get a better than 2 approximation for this problem.

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.

Designing approximate all-pairs distance oracles in the fully dynamic setting is one of the central problems in dynamic graph algorithms. Despite extensive research on this topic, the first result breaking the O(√n) barrier on the update time for any non-trivial approximation was introduced only recently by Forster, Goranci and Henzinger [SODA’21] who achieved m1/ρ+o(1) amortized update time with a O(log n)3ρ−2 factor in the approximation ratio, for any parameter ρ ≥ 1. In this paper, we give the first constant-stretch fully dynamic distance oracle with small polynomial update and query time. Prior work required either at least a poly-logarithmic approximation or much larger update time. Our result gives a more fine-grained trade-off between stretch and update time, for instance we can achieve constant stretch of O(1/ρ2)4/ρ in amortized update time Õ(nρ), and query time Õ(nρ/8) for any constant parameter 0 < ρ < 1. Our algorithm is randomized and assumes an oblivious adversary. A core technical idea underlying our construction is to design a black-box reduction from decremental approximate hub-labeling schemes to fully dynamic distance oracles, which may be of independent interest. We then apply this reduction repeatedly to an existing decremental algorithm to bootstrap our fully dynamic solution.

A $t$-emulator of a graph $G$ is a graph $H$ that approximates its pairwise shortest path distances up to multiplicative $t$ error. We study fault tolerant $t$-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior. In particular, our main result is that, for $(2k-1)$-emulators with $k$ odd, we can tolerate a polynomial number of edge faults for free. For example: for any $n$-node input graph, we construct a $5$-emulator ($k=3$) on $O(n^{4/3})$ edges that is robust to $f = O(n^{2/9})$ edge faults. It is well known that $Ω(n^{4/3})$ edges are necessary even if the $5$-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd $k$, and whether a similar phenomenon can be proved for even $k$.

We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in O(loglogn) time.

In this paper, we develop deterministic fully dynamic algorithms for computing approximate distances in a graph with worst-case update time guarantees. In particular, we obtain improved dynamic algorithms that, given an unweighted and undirected graph G = (V, E) undergoing edge insertions and deletions, and a parameter $0 \lt \epsilon \leq 1$, maintain (1 + ϵ)-approximations of the st-distance between a given pair of nodes s and t, the distances from a single source to all nodes (“SSSP”), the distances from multiple sources to all nodes (“MSSP”), or the distances between all nodes (“APSP”). Our main result is a deterministic algorithm for maintaining (1 + ϵ)-approximate st-distance with worst-case update time O(n1.407) (for the current best known bound on the matrix multiplication exponent (ω). This even improves upon the fastest known randomized algorithm for this problem. Similar to several other well-studied dynamic problems whose state-of-the-art worst-case update time is O(n1.407), this matches a conditional lower bound [BNS, FOCS 2019]. We further give a deterministic algorithm for maintaining (1 + ϵ)-approximate single-source distances with worst-case update time O(n1.529), which also matches a conditional lower bound. At the core, our approach is to combine algebraic distance maintenance data structures with near-additive emulator constructions. This also leads to novel dynamic algorithms for maintaining (1 + ϵ, β)-emulators that improve upon the state of the art, which might be of independent interest. Our techniques also lead to improved randomized algorithms for several problems such as exact st-distances and diameter approximation.

Given a weighted undirected graph $G=(V,E,w)$, a hopset $H$ of hopbound $β$ and stretch $(1+ε)$ is a set of edges such that for any pair of nodes $u, v \in V$, there is a path in $G \cup H$ of at most $β$ hops, whose length is within a $(1+ε)$ factor from the distance between $u$ and $v$ in $G$. We show the first efficient decremental algorithm for maintaining hopsets with a polylogarithmic hopbound. The update time of our algorithm matches the best known static algorithm up to polylogarithmic factors. All the previous decremental hopset constructions had a superpolylogarithmic (but subpolynomial) hopbound of $2^{\log^{Ω(1)} n}$ [Bernstein, FOCS'09; HKN, FOCS'14; Chechik, FOCS'18]. By applying our decremental hopset construction, we get improved or near optimal bounds for several distance problems. Most importantly, we show how to decrementally maintain $(2k-1)(1+ε)$-approximate all-pairs shortest paths (for any constant $k \geq 2)$, in $\tilde{O}(n^{1/k})$ amortized update time and $O(k)$ query time. This improves (by a polynomial factor) over the update-time of the best previously known decremental algorithm in the constant query time regime. Moreover, it improves over the result of [Chechik, FOCS'18] that has a query time of $O(\log \log(nW))$, where $W$ is the aspect ratio, and the amortized update time is $n^{1/k}\cdot(\frac{1}ε)^{\tilde{O}(\sqrt{\log n})}$. For sparse graphs our construction nearly matches the best known static running time / query time tradeoff. We also obtain near-optimal bounds for maintaining approximate multi-source shortest paths and distance sketches, and get improved bounds for approximate single-source shortest paths. Our algorithms are randomized and our bounds hold with high probability against an oblivious adversary.

A $k$-spanner of a graph $G$ is a sparse subgraph that preserves its shortest path distances up to a multiplicative stretch factor of $k$, and a $k$-emulator is similar but not required to be a subgraph of $G$. A classic theorem by Thorup and Zwick [JACM '05] shows that, despite the extra flexibility available to emulators, the size/stretch tradeoffs for spanners and emulators are equivalent. Our main result is that this equivalence in tradeoffs no longer holds in the commonly-studied setting of graphs with vertex failures. That is: we introduce a natural definition of vertex fault-tolerant emulators, and then we show a three-way tradeoff between size, stretch, and fault-tolerance for these emulators that polynomially surpasses the tradeoff known to be optimal for spanners. We complement our emulator upper bound with a lower bound construction that is essentially tight (within $\log n$ factors of the upper bound) when the stretch is $2k-1$ and $k$ is either a fixed odd integer or $2$. We also show constructions of fault-tolerant emulators with additive error, demonstrating that these also enjoy significantly improved tradeoffs over those available for fault-tolerant additive spanners.

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.

Data structures that allow efficient distance estimation (distance oracles, distance sketches, etc.) have been extensively studied, and are particularly well studied in centralized models and classical distributed models such as CONGEST. We initiate their study in newer (and arguably more realistic) models of distributed computation: the Congested Clique model and the Massively Parallel Computation (MPC) model. We provide efficient constructions in both of these models, but our core results are for MPC. In MPC we give two main results: an algorithm that constructs stretch/space optimal distance sketches but takes a (small) polynomial number of rounds, and an algorithm that constructs distance sketches with worse stretch but that only takes polylogarithmic rounds. Along the way, we show that other useful combinatorial structures can also be computed in MPC. In particular, one key component we use to construct distance sketches are an MPC construction of the hopsets of Elkin and Neiman (2016). This result has additional applications such as the first polylogarithmic time algorithm for constant approximate single-source shortest paths for weighted graphs in the low memory MPC setting.

We give the first Congested Clique algorithm that computes a sparse hopset with polylogarithmic hopbound in polylogarithmic time. Given a graph G=(V,E), a (β,ε)-hopset H with "hopbound" β, is a set of edges added to G such that for any pair of nodes u and v in G there is a path with at most β hops in G ∪ H with length within (1+ε) of the shortest path between u and v in G. Our hopsets are significantly sparser than the recent construction of [Censor-Hillel et al., 2019], that constructs a hopset of size Õ (n^{3/2}), but with a smaller polylogarithmic hopbound. On the other hand, the previously known construction of sparse hopsets with polylogarithmic hopbound in the Congested Clique model, proposed by [Elkin and Neiman, 2018; Elkin and Neiman, 2019; Elkin and Neiman, 2019], all require polynomial rounds. One tool that we use is an efficient algorithm that constructs an l-limited neighborhood cover, that may be of independent interest. Finally, as a side result, we also give a hopset construction in a variant of the low-memory Massively Parallel Computation model, with improved running time over existing algorithms.

Data structures that allow efficient distance estimation have been extensively studied both in centralized models and classical distributed models. We initiate their study in newer (and arguably more realistic) models of distributed computation: the Congested Clique model and the Massively Parallel Computation (MPC) model. In MPC we give two main results: an algorithm that constructs stretch/space optimal distance sketches but takes a (small) polynomial number of rounds, and an algorithm that constructs distance sketches with worse stretch but that only takes polylogarithmic rounds. Along the way, we show that other useful combinatorial structures can also be computed in MPC. In particular, one key component we use is an MPC construction of the hopsets of Elkin and Neiman (2016). This result has additional applications such as the first polylogarithmic time algorithm for constant approximate single-source shortest paths for weighted graphs in the low memory MPC setting.

Solving linear programs is often a challenging task in distributed settings. While there are good algorithms for solving packing and covering linear programs in a distributed manner (Kuhn et al. 2006), this is essentially the only class of linear programs for which such an algorithm is known. In this work we provide a distributed algorithm for solving a different class of convex programs which we call “distance-bounded network design convex programs”. These can be thought of as relaxations of network design problems in which the connectivity requirement includes a distance constraint (most notably, graph spanners). Our algorithm runs in O((D/ε) log n) rounds in the LOCAL model and with high probability finds a (1+ε)-approximation to the optimal LP solution for any 0 < ε ≤ 1, where D is the largest distance constraint. While solving linear programs in a distributed setting is interesting in its own right, this class of convex programs is particularly important because solving them is often a crucial step when designing approximation algorithms. Hence we almost immediately obtain new and improved distributed approximation algorithms for a variety of network design problems, including Basic 3- and 4-Spanner, Directed k-Spanner, Lowest Degree k-Spanner, and Shallow-Light Steiner Network Design with a spanning demand graph. Our algorithms do not require any “heavy” computation and essentially match the best-known centralized approximation algorithms, while previous approaches which do not use heavy computation give approximations which are worse than the best-known centralized bounds.

In standard randomized (push-pull) rumor spreading, nodes communicate in synchronized rounds. In each round every node contacts a random neighbor in order to exchange the rumor (i.e., either push the rumor to its neighbor or pull it from the neighbor). A natural asynchronous variant of this algorithm is one where each node has an independent Poisson clock with rate 1, and every node contacts a random neighbor whenever its clock ticks. This asynchronous variant is arguably a more realistic model in various settings, including message broadcasting in communication networks, and information dissemination in social networks. In this paper we study how asynchrony affects the rumor spreading time, that is, the time before a rumor originated at a single node spreads to all nodes in the graph. Our first result states that the asynchronous push-pull rumor spreading time is asymptotically bounded by the standard synchronous time. Precisely, we show that for any graph G on n-nodes, where the synchronous push-pull protocol informs all nodes within T(G) rounds with high probability, the asynchronous protocol needs at most time O(T(G)+log n) to inform all nodes with high probability. On the other hand, we show that the expected synchronous push-pull rumor spreading time is bounded by O(√ n) times the expected asynchronous time. These results improve upon the bounds for both directions shown recently by Acan et al. (PODC 2015). An interesting implication of our first result is that in regular graphs, the weaker push-only variant of synchronous rumor spreading has the same asymptotic performance as the synchronous push-pull algorithm.