We present parallel algorithms for computing single-source reachability and shortest paths on directed n-vertex m-edge graphs using near-linear Õ(m) work and o(√n) depth whenever m ≥ n^{1+o(1)}. At the extreme of m = Ω(n²), our reachability and shortest path algorithms have depth only n^0.136 and n^{0.25+o(1)}, respectively. The state-of-the-art parallel algorithms with near-linear work for both problems [Jambulapati et al., 2019; Cao et al., 2020; Rozhoň et al., 2023; Cao and Fineman, 2023; Brand et al., 2025] require Ω(√n) depth in all density regimes.

We give the first algorithms that, with high probability, maintain (1-ε)-approximate s-t maximum flow in an n-vertex undirected, capacitated graph undergoing either only edge insertions or only edge deletions in total update time Õ_ε(n²). For dense graphs, this yields polylogarithmic amortized update time, which was previously only obtained for the special case of uncapacitated graphs undergoing edge insertions. We develop the following two algorithms: - For graphs undergoing deletions, we generalize the congestion-balancing framework from [Aaron Bernstein et al., 2020], which was developed for maximum matching. We then show that this framework can be simulated on cut sparsifiers, which yields significant speed-ups. - For graphs undergoing insertions, we show that the sparsification techniques by Eppstein et al. [Eppstein et al., 1997] can be combined more directly with the techniques from Henzinger and Goranci [Goranci and Henzinger, 2023]. We thereby bypass the need to dynamize the more involved residual graph sparsification approach by Levin and Karger [Karger and Levine, 2015] suggested in [Goranci et al., 2025], and extend their result to capacitated graphs.

Given an undirected graph \(G = (V, E, w)\), a Gomory-Hu tree \(T\) (Gomory and Hu, 1961) is a tree on \(V\) that preserves all-pairs mincuts of \(G\) exactly.

Whether a graph \(G = (V,E)\) is connected is arguably its most fundamental property. Naturally, connectivity was the first characteristic studied for dynamic graphs, i.e. graphs that undergo edge insertions and deletions. While connectivity algorithms with polylogarithmic amortized update time have been known since the 90s, achieving worst-case guarantees has proven more elusive.

Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions \(e_1, e_2, \ldots, e_k\) to an \(m\)-edge graph \(G\) that is initially a \(\phi\)-expander, the algorithm can grow a set \(P \subseteq V\) such that at any time \(t\), \(G[V \setminus P]\) is an expander of the same quality as the initial graph \(G\) up to a constant factor and the set \(P\) has volume at most \(O(t / \phi)\). However, currently, there is no algorithm to grow \(P\) with low worst-case recourse that achieves any non-trivial guarantee.

We aim to revive Thorup’s conjecture [Thorup, WG’92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph G=(V,E) with m edges, we can add m1+o(1) “shortcut” edges E+ from the transitive closure E* of G so that G+(u,v) ≤ mo(1) for all (u,v)∈ E*, where G+=(V,E∪ E+). The conjecture was refuted by Hesse [Hesse, SODA’03], followed by significant efforts in the last few years to optimize the lower bounds.

Given an undirected, weighted graph $G=(V, E, w)$, a Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a tree T over the vertex set V such that for every pair of vertices $s, t \in V$, the ($s, t$) min-cut in T is also an ($s, t$) min-cut in G and has the same value. In this article, we give the first deterministic almost-linear-time algorithm for constructing a Gomory-Hu tree. Our algorithm runs in $m^{1+o(1)}$-time, where m denotes the number of edges in the input graph G; this is clearly optimal up to the $m^{o(1)}$ term in the running time. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $n m^{1+o(1)}$ time using current maxflow algorithms. In fact, our algorithm is also the first almost-linear-time deterministic algorithm for even simpler problems, such as finding the k-edge-connected components of a graph. Our new result hinges on two separate and novel components that each introduce a distinct set of de-randomization tools of independent interest: - a deterministic reduction from the all-pairs min-cuts problem to the single-source min-cuts problem incurring only sub-polynomial overhead, and - a deterministic almost-linear time algorithm for the singlesource min-cuts problem.

We present a new and surprisingly simple analysis of random-shift decompositions-originally proposed by Miller, Peng, and Xu [SPAA’13]: We show that decompositions for exponentially growing scales $D=2^{0}, 2^{1}, \ldots, 2^{\log _{2}(\operatorname{diam}(G))}$, have a tight constant trade-off between distance-to-center and separation probability on average across the distance scales - opposed to a necessary $\Omega(\log n)$ trade-off for a single scale. This almost immediately yields a way to compute a tree T for graph G that preserves all graph distances with expected $O(\log n)$-stretch. This gives an alternative proof that obtains tight approximation bounds of the seminal result by Fakcharoenphol, Rao, and Talwar [STOC’03] matching the $\Omega(\log n)$ lower bound by Bartal [FOCS’96]. Our insights can also be used to refine the analysis of a simple $\ell_{1}$-oblivious routing proposed in [FOCS’22], yielding a tight $O(\log n)$ competitive ratio. Our algorithms for constructing tree embeddings and $\ell_{1}$ oblivious routings can be implemented in the sequential, parallel, and distributed settings with optimal work, depth, and rounds, up to polylogarithmic factors. Previously, fast algorithms with tight guarantees were not known for tree embeddings in parallel and distributed settings, and for $\ell_{1}$-oblivious routings, not even a fast sequential algorithm was known.

In this work, we present the first algorithm to compute expander decompositions in an m-edge directed graph with near-optimal time Õ(m). Further, our algorithm can maintain such a decomposition in a dynamic graph and again obtains near-optimal update times. Our result improves over previous algorithms [Bernstein et al., 2020; Hua et al., 2023] that only obtained algorithms optimal up to subpolynomial factors. In order to obtain our new algorithm, we present a new push-pull-relabel flow framework that generalizes the classic push-relabel flow algorithm [Goldberg and Tarjan, 1988] which was later dynamized for computing expander decompositions in undirected graphs [Henzinger et al., 2020; Saranurak and Wang, 2019]. We then show that the flow problems formulated in recent work [Hua et al., 2023] to decompose directed graphs can be solved much more efficiently in the push-pull-relabel flow framework. Recently, our algorithm has already been employed to obtain the currently fastest algorithm to compute min-cost flows [Van Den Brand et al., 2024]. We further believe that our algorithm can be used to speed-up and simplify recent breakthroughs in combinatorial graph algorithms towards fast maximum flow algorithms [Chuzhoy and Khanna, 2024; Chuzhoy and Khanna, 2024; Bernstein et al., 2024].

Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph G = (V, E), a near-optimal ø-expander decomposition is a partition V1, V2,. ., Vk of the vertex set V where each subgraph G [Vi] is a ø-expander, and only an Õ (ø )-fraction of the edges cross between partition sets.

We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in \(m^{1+o(1)}\) time. Our algorithm builds the flow through a sequence of \(m^{1+o(1)}\) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized \(m^{o(1)}\) time using a new dynamic graph data structure. Our framework extends to algorithms running in \(m^{1+o(1)}\) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p -norm flows, and p -norm isotonic regression on arbitrary directed acyclic graphs.

We give the first almost-linear total time algorithm for deciding if a flow of cost at most$F$still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, and cost increases. This implies almost-linear time algorithms for approximating the minimum-cost flow value and s-t distance on such decremental graphs. Our framework additionally allows us to maintain decremental strongly connected components in almost-linear time deterministically. These algorithms also improve over the current best known runtimes for statically computing minimum-cost flow, in both the randomized and deterministic settings. We obtain our algorithms by taking the dual perspective, which yields cut-based algorithms. More precisely, our algorithm computes the flow via a sequence of$m^{1+o(1)}$-dynamic min-ratio cut problems, the dual analog of the dynamic min-ratio cycle problem that underlies recent fast algorithms for minimum-cost flow. Our main technical contribution is a new data structure that returns an approximately optimal min-ratio cut in amortized$m^{o(1)}$time by maintaining a tree-cut sparsifier. This is achieved by devising a new algorithm to maintain the dynamic expander hierarchy of [$\text{Goranci-Racke-}$SaranurakTan, SODA 2021] that also works in capacitated graphs. All our algorithms are deterministc, though they can be sped up further using randomized techniques while still working against an adaptive adversary.

We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an$n-\mathbf{vertex}$planar graph$G=(V, E)$undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a$(1+\epsilon)-\mathbf{approximate}$dynamic algorithm that supports edge updates and distance queries in$n^{o(1)}$time, for any$1/\mathbf{poly}(\log n) < \epsilon < 1$. Our result is a significant improvement over the best previously known bound of$\tilde{O}(\sqrt{n})$on update and query time due to [Abraham, Chechik, and Gavoille, STOC ’12], and bypasses a$\Omega(\sqrt{n})$conditional lower-bound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS ’16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chang, Krauthgamer, Tan, STOC ’22].

In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an m-edge graph G = (V, E) that is a Φ-expander, i.e. where |∂ S| ≥ Φ ⋅ vol(S) for every S ⊆ V, vol(S) ≤ vol(V)/2. Beyond its simplicity and structural importance, this question is well-motivated by the current state-of-the-art of fast algorithms for 𝓁_∞ oblivious routings that reduce to the expander-case which is in turn solved by electrical flow routing. Our main result proves that the electrical routing is an O(Φ^{-1} log m)-competitive oblivious routing in the 𝓁₁- and 𝓁_∞-norms. We further observe that the oblivious routing is O(log² m)-competitive in the 𝓁₂-norm and, in fact, O(log m)-competitive if 𝓁₂-localization is O(log m) which is widely believed. Using these three upper bounds, we can smoothly interpolate to obtain upper bounds for every p ∈ [2, ∞] and q given by 1/p + 1/q = 1. Assuming 𝓁₂-localization in O(log m), we obtain that in 𝓁_p and 𝓁_q, the electrical oblivious routing is O(Φ^{-(1-2/p)}log m) competitive. Using the currently known result for 𝓁₂-localization, this ratio deteriorates by at most a sublogarithmic factor for every p, q ≠ 2. We complement our upper bounds with lower bounds that show that the electrical routing for any such p and q is Ω(Φ^{-(1-2/p)} log m)-competitive. This renders our results in 𝓁₁ and 𝓁_∞ unconditionally tight up to constants, and the result in any 𝓁_p- and 𝓁_q-norm to be tight in case of 𝓁₂-localization in O(log m).

We provide an algorithm which, with high probability, maintains a (1 — ɛ)-approximate maximum flow on an undirected graph undergoing m-edge additions in amortized mo(1)ɛ-3 time per update. To obtain this result, we provide a more general algorithm that solves what we call the incremental, thresholded, p-norm flow problem that asks to determine the first edge-insertion in an undirected graph that causes the minimum ℓp-norm flow to decrease below a given threshold in value. Since we solve this thresholded problem, our data structure succeeds against an adaptive adversary that can only see the data structure's output. Furthermore, since our algorithm holds for p = 2, we obtain improved algorithms for dynamically maintaining the effective resistance between a pair of vertices in an undirected graph undergoing edge insertions.

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, s-t shortest path, maximum flow, and minimum-cost flow. To solve these problems, we give a deterministic data structure that returns a mo(1)-approximate minimum-ratio cycle in fully dynamic graphs in amortized mo(1) time per update. Combining this with the interior point method framework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear time algorithm for deciding the first update in an incremental graph after which the cost of the minimum-cost flow attains value at most some given threshold F. By rather direct reductions to minimum-cost flow, we are then able to solve the problems in incremental graphs mentioned above.

We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in graphs undergoing edge insertions and/or deletions. In particular, we obtain the following results:

We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities. As a consequence, we obtain the first running time improvement for deterministic algorithms that compute maximum-flow in graphs with polynomial bounded capacities since the work of Goldberg-Rao [J.ACM ’98].Our algorithm builds on the framework of Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS ’22] that computes an optimal flow by computing a sequence of $m^{1+o(1)}$-approximate undirected minimum-ratio cycles. We develop a deterministic dynamic graph data-structure to compute such a sequence of minimum-ratio cycles in an amortized $m^{o(1)}$ time per edge update. Our key technical contributions are deterministic analogues of the vertex sparsification and edge sparsification components of the data-structure from Chen et al. For the vertex sparsification component, we give a method to avoid the randomness in Chen et al. which involved sampling random trees to recurse on. For the edge sparsification component, we design a deterministic algorithm that maintains an embedding of a dynamic graph into a sparse spanner. We also show how our dynamic spanner can be applied to give a deterministic data structure that maintains a fully dynamic low-stretch spanning tree on graphs with polynomially bounded edge lengths, with subpolynomial average stretch and subpolynomial amortized time per edge update.

In this article, we show that the algorithm of maintaining expander decompositions in graphs undergoing edge deletions directly by removing sparse cuts repeatedly can be made efficient. Formally, for an m-edge undirected graph G, we say a cut is ϕ-sparse if . A ϕ-expander decomposition of G is a partition of V into sets X1,X2,…, Xk such that each cluster G[X1] contains no ϕ-sparse cut (meaning it is a ϕ-expander) with Õ(ϕm) edges crossing between clusters. A natural way to compute a ϕ-expander decomposition is to decompose clusters by ϕ-sparse cuts until no such cut is contained in any cluster. We show that even in graphs undergoing edge deletions, a slight relaxation of this meta-algorithm can be implemented efficiently with amortized update time mo(1)/ϕ2. Our approach naturally extends to maintaining directed ϕ-expander decompositions and ϕ-expander hierarchies and thus gives a unifying framework while having simpler proofs than previous state-of-the-art work. In all settings, our algorithm matches the run-times of previous algorithms up to subpolynomial factors. Moreover, our algorithm provides stronger guarantees for ϕ-expander decompositions. For example, for graphs undergoing edge deletions, our approach is the first to maintain a dynamic expander decomposition where each updated decomposition is a refinement of the previous decomposition, and our approach is the first to guarantee a sublinear ϕm1+ο(1) bound on the total number of edges that cross between clusters across the entire sequence of dynamic updates. Our techniques also give by far the simplest, deterministic algorithms for maintaining Strongly-Connected Components (SCCs) in directed graphs undergoing edge deletions, and for maintaining connectivity in undirected fully-dynamic graphs, both matching the current state-of-the art run-times up to subpolynomial factors. * The full version of the paper can be accessed at https://arxiv.org/abs/2204.02519

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.

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using a new dynamic graph data structure. Our framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.

In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear in the number of non-zero entries of L. Previous reductions imply the first deterministic almost-linear time algorithms for computing various fundamental quantities on directed graphs including stationary distributions, personalized PageRank, hitting times and escape probabilities.We obtain these results by introducing partial symmetrization, a new technique that makes the Laplacian of an Eulerian directed graph “less directed” in a useful sense, which may be of independent interest. The usefulness of this technique comes from two key observations: Firstly, the partially symmetrized Laplacian preconditions the original Eulerian Laplacian well in Richardson iteration, enabling us to construct a solver for the original matrix from a solver for the partially symmetrized one. Secondly, the undirected structure in the partially symmetrized Laplacian makes it possible to sparsify the matrix very crudely, i.e. with large spectral error, and still show that Richardson iterations convergence when using the sparsified matrix as a preconditioner. This allows us to develop deterministic sparsification tools for the partially symmetrized Laplacian.Together with previous reductions from directed Laplacians to Eulerian Laplacians, our technique results in the first deterministic almost-linear time algorithm for solving linear equations in directed Laplacians. To emphasize the generality of our new technique, we show that two prominent existing (randomized) frameworks for solving linear equations in Eulerian Laplacians can be derandomized in this way: the squaring-based framework of [1] and the sparsified Cholesky-based framework of [2].

Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees, matchings, and single-source shortest paths, very little was known for an important primitive like graph sparsifiers. The challenge is how to approximately preserve so much information about the graph (e.g., all-pairs distances and all cuts) without revealing the algorithms' underlying randomness to the adaptive adversary. In this paper we present the first non-trivial efficient adaptive algorithms for maintaining spanners and cut sparisifers. These algorithms in turn imply improvements over existing algorithms for other problems. Our first algorithm maintains a polylog$(n)$-spanner of size $\tilde O(n)$ in polylog$(n)$ amortized update time. The second algorithm maintains an $O(k)$-approximate cut sparsifier of size $\tilde O(n)$ in $\tilde O(n^{1/k})$ amortized update time, for any $k\ge1$, which is polylog$(n)$ time when $k=\log(n)$. The third algorithm maintains a polylog$(n)$-approximate spectral sparsifier in polylog$(n)$ amortized update time. The amortized update time of both algorithms can be made worst-case by paying some sub-polynomial factors. Prior to our result, there were near-optimal algorithms against oblivious adversaries (e.g. Baswana et al. [TALG'12] and Abraham et al. [FOCS'16]), but the only non-trivial adaptive dynamic algorithm requires $O(n)$ amortized update time to maintain $3$- and $5$-spanner of size $O(n^{1+1/2})$ and $O(n^{1+1/3})$, respectively [Ausiello et al. ESA'05]. Our results are based on two novel techniques. The first technique, is a generic black-box reduction that allows us to assume that the graph undergoes only edge deletions and, more importantly, remains an expander with almost-uniform degree. The second technique we call proactive resampling. [...]

We study linear equations in combinatorial Laplacians of k-dimensional simplicial complexes (k-complexes), a natural generalization of graph Laplacians. Combinatorial Laplacians play a crucial role in homology and are a central tool in topology. Beyond this, they have various applications in data analysis and physical modeling problems. It is known that nearly-linear time solvers exist for graph Laplacians. However, nearly-linear time solvers for combinatorial Laplacians are only known for restricted classes of complexes. This paper shows that linear equations in combinatorial Laplacians of 2-complexes are as hard to solve as general linear equations. More precisely, for any constant c ≥ 1, if we can solve linear equations in combinatorial Laplacians of 2-complexes up to high accuracy in time Õ((# of nonzero coefficients)^c), then we can solve general linear equations with polynomially bounded integer coefficients and condition numbers up to high accuracy in time Õ((# of nonzero coefficients)^c). We prove this by a nearly-linear time reduction from general linear equations to combinatorial Laplacians of 2-complexes. Our reduction preserves the sparsity of the problem instances up to poly-logarithmic factors.

In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph G undergoes a sequence of edge weight updates and the goal is to maintain a data structure on G, that can quickly answer distance queries between any two vertices x,y ∊ V(G). The currently best algorithms [FOCS'01, SODA'05] for this problem require Õ(n2/3) worst-case update and query time, while conditional lower bounds [FOCS'16] show that either update or query time is needed1. In this article, we present the first algorithm with near-optimal worst-case update and query time for the offline setting, where the update sequence is given initially. This result is obtained by giving the first offline dynamic algorithm for maintaining dense distance graphs (DDGs) faster than recomputing from scratch after each update. Further, we also present an online algorithm for the incremental APSP problem with worst-case update/query time. This allows us to reduce the online dynamic APSP problem to the online decremental APSP problem, which constitutes partial progress even for the online version of this notorious problem.

Given a directed, weighted graph G = (V, E) undergoing edge insertions, the incremental single-source shortest paths (SSSP) problem asks for the maintenance of approximate distances from a dedicated source s while optimizing the total time required to process the insertion sequence of m edges. Recently, Gutenberg, Williams and Wein [STOC'20] introduced a deterministic Õ(n2) algorithm for this problem, achieving near linear time for very dense graphs. For sparse graphs, Chechik and Zhang [SODA'21] recently presented a deterministic Õ(m5/3) algorithm, and an adaptive randomized algorithm with run-time . This algorithm is remarkable for two reasons: 1) in very spare graphs it reaches the directed hopset barrier of Ω(n3/2) that applied to all previous approaches for partially-dynamic SSSP [STOC'14, SODA'20, FOCS'20] and 2) it does not resort to a directed hopset technique itself. In this article we introduce propagation synchronization, a new technique for controlling the error build-up on paths throughout batches of insertions. This leads us to a significant improvement of the approach in [SODA'21] yielding a deterministic O(m3/2) algorithm for the problem. By a very careful combination of our new technique with the sampling approach from [SODA'21], we further obtain an adaptive randomized algorithm with total update time Õ(m4/3). This is the first partially-dynamic SSSP algorithm in sparse graphs to bypass the notorious directed hopset barrier which is often seen as the fundamental challenge towards achieving truly near-linear time algorithms.

In the decremental single-source shortest paths problem, the goal is to maintain distances from a fixed source$s$to every vertex$v$in an m-edge graph undergoing edge deletions. In this paper, we conclude a long line of research on this problem by showing a near-optimal deterministic data structure that maintains (1 + E) -approximate distance estimates and runs in m1+o(1)total update time. Our result, in particular, removes the oblivious adversary assumption required by the previous breakthrough result by Henzinger et al. [FOCS'14], which leads to our second result: the first almost-linear time algorithm for (1 - E) -approximate min-cost flow in undirected graphs where capacities and costs can be taken over edges and vertices. Previously, algorithms for max flow with vertex capacities, or min-cost flow with any capacities required super-linear time. Our result essentially completes the picture for approximate flow in undirected graphs. The key technique of the first result is a novel framework that allows us to treat low-diameter graphs like expanders. This allows us to harness expander properties while bypassing shortcomings of expander decomposition, which almost all previous expander-based algorithms needed to deal with. For the second result, we break the notorious flow-decomposition barrier from the multiplicative-weight-update framework using randomization.

Given a directed graph $G = (V,E)$, undergoing an online sequence of edge deletions with $m$ edges in the initial version of $G$ and $n = |V|$, we consider the problem of maintaining all-pairs shortest paths (APSP) in $G$. Whilst this problem has been studied in a long line of research [ACM'81, FOCS'99, FOCS'01, STOC'02, STOC'03, SWAT'04, STOC'13] and the problem of $(1+ε)$-approximate, weighted APSP was solved to near-optimal update time $\tilde{O}(mn)$ by Bernstein [STOC'13], the problem has mainly been studied in the context of oblivious adversaries, which assumes that the adversary fixes the update sequence before the algorithm is started. In this paper, we make significant progress on the problem in the setting where the adversary is adaptive, i.e. can base the update sequence on the output of the data structure queries. We present three new data structures that fit different settings: We first present a deterministic data structure that maintains exact distances with total update time $\tilde{O}(n^3)$. We also present a deterministic data structure that maintains $(1+ε)$-approximate distance estimates with total update time $\tilde O(\sqrt{m} n^2/ε)$ which for sparse graphs is $\tilde O(n^{2+1/2}/ε)$. Finally, we present a randomized $(1+ε)$-approximate data structure which works against an adaptive adversary; its total update time is $\tilde O(m^{2/3}n^{5/3} + n^{8/3}/(m^{1/3}ε^2))$ which for sparse graphs is $\tilde O(n^{2+1/3})$. Our exact data structure matches the total update time of the best randomized data structure by Baswana et al. [STOC'02] and maintains the distance matrix in near-optimal time. Our approximate data structures improve upon the best data structures against an adaptive adversary which have $\tilde{O}(mn^2)$ total update time [JACM'81, STOC'03].

Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information. Spanners and emulators serve this purpose. Unfortunately, very little is known about dynamically maintaining sparse spanners and emulators as the graph is modified by a sequence of edge insertions and deletions. This paper develops fast dynamic algorithms for spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight. For unweighted undirected m-edge n-node graphs we obtain the following results. Under the popular OMv conjecture, there can be no decremental or incremental algorithm that maintains an n1+o(1) edge (purely additive) +nδ-emulator for any δ < 1/2 with arbitrary polynomial preprocessing time and total update time m1+o(1). Also, under the Combinatorial k-Clique hypothesis, any fully dynamic combinatorial algorithm that maintains an n1+o(1) edge (1 + ∊, no(1))-spanner or emulator for small ∊ must either have preprocessing time mn1–o(1) or amortized update time m1–o(1). Both of our conditional lower bounds are tight. As the above fully dynamic lower bound only applies to combinatorial algorithms, we also develop an algebraic spanner algorithm that improves over the m1–o(1) update time for dense graphs. For any constant ∊ ∊ (0, 1], there is a fully dynamic algorithm with worst-case update time O(n1.529) that whp maintains an n1+o(1) edge (1 + ∊, no(1))-spanner. Our new algebraic techniques allow us to also obtain a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP) that can perform both edge updates and can report shortest paths in worst-case time O(n1.9), which are correct whp. This is the first path-reporting fully dynamic APSP algorithm with a truly subquadratic query time that beats O(n2.5) update time. It works against an oblivious adversary. Finally, we give two applications of our new dynamic spanner algorithms: (1) a fully dynamic (1 + ∊)-approximate APSP algorithm with update time O(n1.529) that can report approximate shortest paths in n1+o(1) time per query; previous subquadratic update/query algorithms could only report the distance, but not obtain the paths; (2) a fully dynamic algorithm for near-2-approximate Steiner tree maintenance with both terminal and edge updates.

Let G=(V, E, w) be a weighted, directed graph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed source s and the goal is to maintain a data structure that can answer path-queries s\rightarrowtail v for any v ∈ V. In the more general single-source shortest paths (SSSP) problem the goal is to return an approximate shortest path to v, and in the SCC problem the goal is to maintain strongly connected components of G and to answer path queries within each component. All of these problems have been very actively studied over the past two decades, but all the fast algorithms are randomized and, more significantly, they can only answer path queries if they assume a weaker model: they assume an oblivious adversary which is not adaptive and must fix the update sequence in advance. This assumption significantly limits the use of these data structures, most notably preventing them from being used as subroutines in static algorithms. All the above problems are notoriously difficult in the adaptive setting. In fact, the state-of-the-art is still the Even and Shiloach tree, which dates back all the way to 1981 [1] and achieves total update time O(mn). We present the first algorithms to break through this barrier. i) deterministic decremental SSR/SSC with total update time mn2/3+o(1)ii) deterministic decremental SSSP with total update time n2+2/3+o(1)To achieve these results, we develop two general techniques for working with dynamic graphs. The first generalizes expander-based tools to dynamic directed graphs. While these tools have already proven very successful in undirected graphs, the underlying expander decomposition they rely on does not exist in directed graphs. We thus need to develop an efficient framework for using expanders in directed graphs, as well as overcome several technical challenges in processing directed expanders. We establish several powerful primitives that we hope will pave the way for other expander-based algorithms in directed graphs. The second technique, which we call congestion balancing, provides a new method for maintaining flow under adversarial deletions. The results above use this technique to maintain an embedding of an expander. The technique is quite general, and to highlight its power, we use it to achieve the following additional result: iii) The first near-optimal algorithm for decremental bipartite matching.

In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph G = (V, E, w) undergoing edge deletions and a source vertex r ∈ V; let n=|V|, m=|E| and W be the aspect ratio of the graph. The goal is to obtain a data structure that maintains shortest paths from r to all vertices in V and can answer distance queries in O(1) time, as well as return the corresponding path P in O(|P|) time. This problem was first considered by Even and Shiloach [JACM'81], who provided an algorithm with total update time O(mn) for unweighted undirected graphs; this was later extended to directed weighted graphs [FOCS'95, STOC'99]. There are conditional lower bounds showing that O(mn) is in fact near-optimal [ESA'04, FOCS'14, STOC'15, STOC'20]. In a breakthrough result, Forster et al. showed that total update time min{m7/6n2/3+o(1), m3/4n5/4+o(1)} polylog(W) = mn0.9+o(1)polylog (W), is possible if the algorithm is allowed to return ( 1 +ε)-approximate paths, instead of exact ones [STOC'14, ICALP'15]. No further progress was made until Probst Gutenberg and Wulff-Nilsen [SODA'20] provided a new approach for the problem, which yields total time ~O(min{m2/3n4/3logW, (mn)7/8logW}) = ~O(min{n8/3logW, mn3/4logW}). Our result builds on this recent approach, but overcomes its limitations by introducing a significantly more powerful abstraction, as well as a different core subroutine. Our new framework yields a decremental ( 1+ε)-approximate SSSP data structure with total update time ~O(n2log4W/ε). Our algorithm is thus near-optimal for dense graphs with polynomial edge-weights. Our framework can also be applied to sparse graphs to obtain total update time ~O(mn2/3log3W/ε). Combined, these data structures dominate all previous results. Like all previous o(mn) algorithms that can return a path (not just a distance estimate), our result is randomized and assumes an oblivious adversary. Our framework effectively allows us to reduce SSSP in general graphs to the same problem in directed acyclic graphs (DAGs). We believe that our framework has significant potential to influence future work on directed SSSP, both in the dynamic model and in others.

In the decremental (1 + ϵ)-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph G = (V, E) with n = |V|, m = |E|, undergoing edge deletions, and a distinguished source s ϵ V, and we are asked to process edge deletions efficiently and answer queries for distance estimates G(s, v) for each v ϵ V, at any stage, such that G(s, v) ≤ G(s, v) ≤ (1 + ϵ)distG(s, v). In the decremental (1 + ϵ)-approximate All-Pairs Shortest Path (APSP) problem, we are asked to answer queries for distance estimates G(u, v) for every u,v ϵ V. In this article, we consider the problems for undirected, unweighted graphs. We present a new deterministic algorithm for the decremental (1 + ϵ)-approximate SSSP problem that takes total update time O(mn0.5+o(1)). Our algorithm improves on the currently best algorithm for dense graphs by Chechik and Bernstein [STOC 2016] with total update time Õ(n2) and the best existing algorithm for sparse graphs with running time [SODA 2017] whenever m = O(n1.5−o(1)). In order to obtain our new algorithm, we develop several new techniques including improved decremental cover data structures for graphs, a more efficient notion of the heavy/light decomposition framework introduced by Chechik and Bernstein and the first clustering technique to maintain a dynamic sparse emulator in the deterministic setting. As a by-product, we also obtain a new simple deterministic algorithm for the decremental (1 + ϵ)-approximate APSP problem with near-optimal total running time Õ(mn/ϵ) matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].

Given a dynamic digraph G = (V, E) undergoing edge deletions and given s ϵ V and constant ϵ with 0 < ϵ ≤ 1, we consider the problem of maintaining (1+ϵ)-approximate shortest path distances from s to all vertices in G over the sequence of deletions. Even and Shiloach (J. ACM’81) give a deterministic data structure for the exact version of the problem in unweighted graphs with total update time O(mn). Henzinger et al. (STOC’14, ICALP’15) give a Monte Carlo data structure for the approximate version with an improved total update time bound of O(mn0.9+°(1) log W) with better bounds for sufficiently dense and sufficiently sparse graphs; here W is the ratio between the largest and smallest edge weight. A drawback of their data structure and in fact of all previous randomized data structures is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This severely limits its application as a black box inside algorithms. We present the following (1 + ϵ)-approximate data structures: the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time Õ(m2/3n4/3)1 for unweighted graphs and Õ(m3/4n5/4 log W) for weighted graphs, the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time for unweighted graphs and Õ(m2/3n4/3 log W) for weighted graphs, the third data structure is Monte Carlo and is correct w.h.p. against an oblivious adversary; it has total expected update time Õ((mn)7/8 log W) = Õ(mn3/4 log W). Each of our data structures can report the length of a (1 + ϵ)-approximate shortest path from s to any query vertex in constant time at any point during the sequence of updates; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al. for all graph densities. For instance, when m = Θ(n2), our second result improves their bound from O(n2+3/4+o(1) log W) to Õ(n2+1/2) in the unweighted setting and to Õ(n2+2/3 log W) in the weighted setting. When m = Θ(n), our third result gives an improvement from O(n1+5/6+o(1) log W) to Õ(n1+3/4 log W). Furthermore, our first data structure is the first to improve on the O(mn) bound of Even and Shiloach for all but the sparsest graphs while still working against an adaptive adversary and works even in weighted graphs; this answers an open problem by Henzinger et al.

Given a directed weighted graph G = (V, E) undergoing vertex insertions and deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance matrix to the current version of G. In two breakthrough results, Italiano and Demetrescu [STOC'03] presented an algorithm that requires Õ(n2) amortized update time, and Thorup showed in [STOC'05] that worst-case update time Õ(n2+3/4) can be achieved. In this article, we make substantial progress on the problem. We present the following new results: We present the first deterministic data structure that breaks the Õ(n2+3/4) worst-case update time bound by Thorup which has been standing for almost 15 years. We improve the worst-case update time to Õ(n2+5/7) = Õ(n2.71) and to Õ(n2+3/5) = Õ(n2.6) for unweighted graphs. We present a simple deterministic algorithm with Õ(n2+3/4) worst-case update time (Õ(n2+2/3) for unweighted graphs), and a simple Las-Vegas algorithm with worst-case update time Õ(n2+2/3) (Õ(n2+1/2) for unweighted graphs) that works against a non-oblivious adversary. Both data structures require space Õ(n2). These are the first exact dynamic algorithms with trulysubcubic update time and space usage. This makes significant progress on an open question posed in multiple articles [COCOON'01, STOC '03, ICALP '04, Encyclopedia of Algorithms '08] and is critical to algorithms in practice [TALG '06] where large space usage is prohibitive. Moreover, they match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time [SODA '17].

In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph G=(V,E) subject to edge insertions and deletions and a source vertex s∈ V, and the goal is to maintain the distance d(s,t) for all t∈ V.

Computing the Strongly-Connected Components (SCCs) in a graph G=(V,E) is known to take only O(m+n) time using an algorithm by Tarjan from 1972[SICOMP 72] where m = |E|, n=|V|. For fully-dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e. graphs that undergo edge deletions.

Computing the strongly connected Components (SCCs) in a graph $G=(V,E)$ is known to take only $O(m + n)$ time using an algorithm by Tarjan [ SIAM J. Comput., 1 (1972), pp. 146--160] where $m = |E|$, $n=|V|$. For fully dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e., graphs that undergo edge deletions. In this paper, we present the first algorithm for general decremental graphs that maintains the SCCs in total update time $\tilde{O}(m)$, thus only a polylogarithmic factor from the optimal running time. (We use $\tilde{O}(f(n))$ notation to suppress logarithmic factors, i.e., $g(n) = \tilde{O}(f(n))$ if $g(n) = O(f(n) {polylog}(n)).$) Our result also yields the fastest algorithm for the decremental single-source reachability (SSR) problem which can be reduced to decrementally maintaining SCCs. Using a well-known reduction, we use our decremental result to achieve new update/query-time trade-offs in the fully dynamic setting. We can maintain the reachability of pairs $S \times V$, $S \subseteq V$ in fully dynamic graphs with update time $\tilde{O}(\frac{|S|m}{t})$ and query time $O(t)$ for all $t \in [1,|S|]$; this matches to polylogarithmic factors the best all-pairs reachability algorithm for $S = V$.

Given a graph $G=(V,E)$ where each vertex is assigned a color from the set $C=\{c_1, c_2, .., c_σ\}$. In the (approximate) nearest colored node problem, we want to query, given $v \in V$ and $c \in C$, for the (approximate) distance $\widehat{\mathbf{dist}}(v, c)$ from $v$ to the nearest node of color $c$. For any integer $1 \leq k \leq \log n$, we present a Color Distance Oracle (also often referred to as Vertex-label Distance Oracle) of stretch $4k-5$ using space $O(knσ^{1/k})$ and query time $O(\log{k})$. This improves the query time from $O(k)$ to $O(\log{k})$ over the best known Color Distance Oracle by Chechik \cite{DBLP:journals/corr/abs-1109-3114}. We then prove a lower bound in the cell probe model showing that our query time is optimal in regard to space up to constant factors. We also investigate dynamic settings of the problem and find new upper and lower bounds.