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 study the approximate maximum weight matching (MWM) problem in a fully dynamic graph subject to edge insertions and deletions. We design meta-algorithms that reduce the problem to the unweighted approximate maximum cardinality matching (MCM) problem. Despite recent progress on bipartite graphs – Bernstein-Dudeja-Langley (STOC 2021) and Bernstein-Chen-Dudeja-Langley-Sidford-Tu (SODA 2025) – the only previous meta-algorithm that applied to non-bipartite graphs suffered a \(\frac12\) approximation loss (Stubbs-Williams, ITCS 2017). We significantly close the weighted-and-unweighted gap by showing the first low-loss reduction that transforms any fully dynamic \((1-\varepsilon)\)-approximate MCM algorithm on bipartite graphs into afully dynamic \((1-\varepsilon)\)–approximate MWM algorithm on general (not necessarily bipartite) graphs, with only a \(\operatorname{poly}(\log n/\varepsilon)\) overhead in the update time. Central to our approach is a new primal–dual framework that reduces the computation of an approximate MWM in general graphs to a sequence of approximate induced matching queries on an auxiliary bipartite extension. In addition, we give the first conditional lower bound on approximate partially dynamic matching with worst-case update time.

We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, based on popular fine-grained complexity hypotheses.

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.

We give a combinatorial algorithm for computing exact maximum flows in directed graphs with n vertices and edge capacities from {1, …, U} in $\tilde O\left({{n^2}\log U}\right)$ time, which is near-optimal on dense graphs. This shaves an no(1)factor from the recent result of [Bernstein–Blikstad–Saranurak–Tu FOCS’24] and, more importantly, greatly simplifies their algorithm. We believe that ours is by a significant margin the simplest of all algorithms that go beyond $\tilde O(m\sqrt n )$ time in general graphs. To highlight this relative simplicity, we provide a full implementation of the algorithm in C++.The only randomized component of our work is the cut-matching game. Via existing tools, we show how to derandomize it for vertex-capacitated max flow and obtain a deterministic $\tilde O\left({{n^2}}\right)$ time algorithm. This marks the first deterministic near-linear time algorithm for this problem (or even for the special case of bipartite matching) in any density regime.

Given a weighted graph G = (V,E,w), a (β, ε)-hopset H is an edge set such that for any s,t ∈ V, where s can reach t in G, there is a path from s to t in G ∪ H which uses at most β hops whose length is in the range [dist_G(s,t), (1+ε)dist_G(s,t)]. We break away from the traditional question that asks for a hopset H that achieves small |H| and small diameter β and instead study the sensitivity of H, a new quality measure. The sensitivity of a vertex (or edge) given a hopset H is, informally, the number of times a single hop in G ∪ H bypasses it; a bit more formally, assuming shortest paths in G are unique, it is the number of hopset edges (s,t) ∈ H such that the vertex (or edge) is contained in the unique st-path in G having length exactly dist_G(s,t). The sensitivity associated with H is then the maximum sensitivity over all vertices (or edges). The highlights of our results are: - A construction for (Õ(√n), 0)-hopsets on undirected graphs with O(log n) sensitivity, complemented with a lower bound showing that Õ(√n) is tight up to polylogarithmic factors for any construction with polylogarithmic sensitivity. - A construction for (n^o(1), ε)-hopsets on undirected graphs with n^o(1) sensitivity for any ε > 0 that is at least inverse polylogarithmic, complemented with a lower bound on the tradeoff between β, ε, and the sensitivity. - We define a notion of sensitivity for β-shortcut sets (which are the reachability analogues of hopsets) and give a construction for Õ(√n)-shortcut sets on directed graphs with O(log n) sensitivity, complemented with a lower bound showing that β = Ω̃(n^{1/3}) for any construction with polylogarithmic sensitivity. We believe hopset sensitivity is a natural measure in and of itself, and could potentially find use in a diverse range of contexts. More concretely, the notion of hopset sensitivity is also directly motivated by the Differentially Private All Sets Range Queries problem [Deng et al. WADS 23]. Our result for O(log n) sensitivity (Õ(√n), 0)-hopsets on undirected graphs immediately improves the current best-known upper bound on utility from Õ(n^{1/3}) to Õ(n^{1/4}) in the pure-DP setting, which is tight up to polylogarithmic factors.

In the restricted shortest paths problem, we are given a graph G whose edges are assigned two non-negative weights: lengths and delays, a source s, and a delay threshold D. The goal is to find, for each target t, the length of the shortest (s, t )-path whose total delay is at most D. While this problem is known to be NP-hard [GJ79], (1 + ε )-approximate algorithms running in Õ (mn ) time1 [GRKL01, LR01] given more than twenty years ago have remained the state-of-the-art for directed graphs. An open problem posed by [Ber12] — who gave a randomized m · no (1) time bicriteria (1 + ε, 1 + ε )-approximation algorithm for undirected graphs — asks if there is similarly an o (mn) time approximation scheme for directed graphs.

In the load-balancing problem, we have an n-vertex bipartite graph G = (L, R, E ) between a set of clients and servers. The goal is to find an assignment of all clients to the servers, while minimizing the maximum load on each server, where load of a server is the number of clients assigned to it. Motivated by understanding the streaming complexity of this problem, we study load-balancing in the one-way (two-party) communication model: the edges of the input graph are partitioned between Alice and Bob, and Alice needs to send a short message to Bob for him to output a solution of the entire graph.

We consider the foundational problem of maintaining a (1 — ε )-approximate maximum weight matching (MWM) in an n-node dynamic graph undergoing edge insertions and deletions. We provide a general reduction that reduces the problem on graphs with a weight range of poly(n ) to poly(1/ε ) at the cost of just an additive poly(1/ε ) in update time. This improves upon the prior reduction of Gupta-Peng (FOCS 2013) which reduces the problem to a weight range of ε-O (1/ε) with a multiplicative cost of O (log n ).

Peer Reviewed

We present a randomized algorithm that computes single-source shortest paths (SSSP) in O ( m log 8 ( n ) log W ) time when edge weights are integral and can be negative. 1 This essentially resolves the classic negative-weight SSSP problem. The previous bounds are \(\tilde{O}((m+n^{1.5})\log W)\) [BLNPSSSW FOCS’20] and m 4/3+ o (1) log W [AMV FOCS’20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS’01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic \(\tilde{O}(m\sqrt {n}\log W)\) bound from over three decades ago [Gabow and Tarjan SICOMP’89].

This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework that reduces negative-weight SSSP in all these setting to $n^{o(1)}$ calls to any SSSP algorithm that works with a virtual source. More specifically, for a graph with $m$ edges, $n$ vertices, undirected hop-diameter $D$, and polynomially bounded integer edge weights, we show randomized algorithms for negative-weight SSSP with (i) $W_{SSSP}(m,n)n^{o(1)}$ work and $S_{SSSP}(m,n)n^{o(1)}$ span, given access to an SSSP algorithm with $W_{SSSP}(m,n)$ work and $S_{SSSP}(m,n)$ span in the parallel model, (ii) $T_{SSSP}(n,D)n^{o(1)}$, given access to an SSSP algorithm that takes $T_{SSSP}(n,D)$ rounds in $\mathsf{CONGEST}$, (iii) $Q_{SSSP}(m,n)n^{o(1)}$ quantum edge queries, given access to a non-negative-weight SSSP algorithm that takes $Q_{SSSP}(m,n)$ queries in the quantum edge query model. This work builds off the recent result of [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], which gives a near-linear time algorithm for negative-weight SSSP in the sequential setting. Using current state-of-the-art SSSP algorithms yields randomized algorithms for negative-weight SSSP with (i) $m^{1+o(1)}$ work and $n^{1/2+o(1)}$ span in the parallel model, (ii) $(n^{2/5}D^{2/5} + \sqrt{n} + D)n^{o(1)}$ rounds in $\mathsf{CONGEST}$, (iii) $m^{1/2}n^{1/2+o(1)}$ quantum queries to the adjacency list or $n^{1.5+o(1)}$ quantum queries to the adjacency matrix. Our main technical contribution is an efficient reduction for computing a low-diameter decomposition (LDD) of directed graphs to computations of SSSP with a virtual source. Efficiently computing an LDD has heretofore only been known for undirected graphs in both the parallel and distributed models.

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with$n$vertices and edge capacities from$\{1, \ldots, U\}$in$n^{2+o(1)}\log U$time, which is almost optimal in dense graphs. Our algorithm is a novel implementation of the classical augmenting-path framework; we list augmenting paths more efficiently using a new variant of the push-relabel algorithm that uses additional edge weights to guide the algorithm, and we derive the edge weights by constructing a directed expander hierarchy. Even in unit-capacity graphs, this breaks the long-standing$O(m \cdot\min\{\sqrt{m},n^{2/3}\})$time bound of the previous combinatorial algorithms by Karzanov (1973) and Even and Tarjan (1975) when the graph has$m=\omega(n^{4/3})$edges. Notably, our approach does not rely on continuous optimization nor heavy dynamic graph data structures, both of which are crucial in the recent developments that led to the almost-linear time algorithm by Chen et al. (FOCS 2022). Our running time also matches the$n^{2+o(1)}$time bound of the independent combinatorial algorithm by Chuzhoy and Khanna (STOC 2024) for computing the maximum bipartite matching, a special case of maximum flow.

The aspect ratio of a (positively) weighted graph $G$ is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in graph algorithms, especially related to the computation of shortest paths. Popular paradigms are to interpolate between the settings of weighted and unweighted input graphs by incurring a dependence on aspect ratio, or by simply restricting attention to input graphs of low aspect ratio. This paper studies the effects of these paradigms, investigating whether graphs of low aspect ratio have more structured shortest paths than graphs in general. In particular, we raise the question of whether one can generally take a graph of large aspect ratio and reweight its edges, to obtain a graph with bounded aspect ratio while preserving the structure of its shortest paths. Our findings are: - Every weighted DAG on $n$ nodes has a shortest-paths preserving graph of aspect ratio $O(n)$. A simple lower bound shows that this is tight. - The previous result does not extend to general directed or undirected graphs; in fact, the answer turns out to be exponential in these settings. In particular, we construct directed and undirected $n$-node graphs for which any shortest-paths preserving graph has aspect ratio $2^{Ω(n)}$. We also consider the approximate version of this problem, where the goal is for shortest paths in $H$ to correspond to approximate shortest paths in $G$. We show that our exponential lower bounds extend even to this setting. We also show that in a closely related model, where approximate shortest paths in $H$ must also correspond to approximate shortest paths in $G$, even DAGs require exponential aspect ratio.

In the weighted load balancing problem, the input is an $n$-vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real weight. The output is an assignment that maps each client to one of its adjacent servers, and the load of a server is then the sum of the weights of the clients assigned to it. The goal is to find an assignment that is well-balanced, typically captured by (approximately) minimizing either the $\ell_\infty$- or $\ell_2$-norm of the server loads. Generalizing both of these objectives, the all-norm load balancing problem asks for an assignment that approximately minimizes all $\ell_p$-norm objectives for $p \ge 1$, including $p = \infty$, simultaneously. Our main result is a deterministic $O(\log{n})$-pass $O(1)$-approximation semi-streaming algorithm for the all-norm load balancing problem. Prior to our work, only an $O(\log{n})$-pass $O(\log{n})$-approximation algorithm for the $\ell_\infty$-norm objective was known in the semi-streaming setting. Our algorithm uses a novel application of the multiplicative weights update method to a mixed covering/packing convex program for the all-norm load balancing problem involving an infinite number of constraints.

For an n-vertex directed graph G = (V, E), a β-shortcut set H is a set of additional edges H ⊆ V × V such that G U H has the same transitive closure as G, and for every pair u, v ∈ V, there is a uv-path in G U H with at most β edges. A natural generalization of shortcut sets to distances is a (β, ε)-hopset H ⊆ V × V, where the requirement is that H and G U H have the same shortest-path distances, and for every u, v ε V, there is a (1 + ε)-approximate shortest path in G U H with at most β edges. There is a large literature on the question of the tradeoff between the optimal size of a shortcut set / hopset and the value of β. In particular we highlight the most natural point on this tradeoff: what is the minimum value of β, such that for any graph G, there exists a β-shortcut set H with O(n) edges? Similarly, what is the minimum value of β such that there exists a (β, ε)-hopset with O(n) edges? Not only is this a very natural structural question in its own right, but shortcuts sets / hopsets form the core of a large number of distributed, parallel, and dynamic algorithms for reachability / shortest paths. A lower bound of Hesse [SODA 2003] for directed graphs shows that if we restrict ourselves to hopsets with O(n) edges, the best we can guarantee is β = Ω(n1/17) for both shortcut sets and hopsets [SODA 2003]; this was later improved to β = Ω(n1/6) by Huang and Pettie [SWAT 2018]. Until very recently the best known upper bound was a folklore construction showing β = O(n1/2), but in a breakthrough result Kogan and Parter [SODA 2022] improve this to β = Õ(n1/3) for shortcut sets and Õ(n2/5) for hopsets. Our result in this paper is to close the gap between shortcut sets and hopsets introduced by the result of Kogan and Parter. That is, we show that for any graph G and any fixed ε there is a (Õ(n1/3), ε) hopset with O(n) edges. Our hopset improves upon the (Õ(n2/5), ε) hopset of Kogan and Parter. More generally, we achieve a smooth tradeoff between hopset size and β which exactly matches the tradeoff of Kogan and Parter for the simpler problem of shortcut sets (up to polylog factors). Additionally, using a very recent black-box reduction of Kogan and Parter, our new hopset immediately implies improved bounds for approximate distance preservers.

We present a randomized algorithm that computes single-source shortest paths (SSSP) in $O\left(m \log ^{8}(n) \log W\right)$ time when edge weights are integral and can be negative.1This essentially resolves the classic negative-weight SSSP problem. The previous bounds are $\tilde{O}\left(\left(m+n^{1.5}\right) \log W\right)$ [BLNPSSSW FOCS’20] and $m^{4 / 3+o(1)} \log W$ [AMV FOCS’20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS’01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic $O(m \sqrt{n} \log W)$ bound from over three decades ago [Gabow and Tarjan SICOMP’89].

Conditional lower bounds for dynamic graph problems has received a great deal of attention in recent years. While many results are now known for the fully-dynamic case and such bounds often imply worst-case bounds for the partially dynamic setting, it seems much more difficult to prove amortized bounds for incremental and decremental algorithms. In this paper we consider partially dynamic versions of three classic problems in graph theory. Based on popular conjectures we show that: -- No algorithm with amortized update time $O(n^{1-\varepsilon})$ exists for incremental or decremental maximum cardinality bipartite matching. This significantly improves on the $O(m^{1/2-\varepsilon})$ bound for sparse graphs of Henzinger et al. [STOC'15] and $O(n^{1/3-\varepsilon})$ bound of Kopelowitz, Pettie and Porat. Our linear bound also appears more natural. In addition, the result we present separates the node-addition model from the edge insertion model, as an algorithm with total update time $O(m\sqrt{n})$ exists for the former by Bosek et al. [FOCS'14]. -- No algorithm with amortized update time $O(m^{1-\varepsilon})$ exists for incremental or decremental maximum flow in directed and weighted sparse graphs. No such lower bound was known for partially dynamic maximum flow previously. Furthermore no algorithm with amortized update time $O(n^{1-\varepsilon})$ exists for directed and unweighted graphs or undirected and weighted graphs. -- No algorithm with amortized update time $O(n^{1/2 - \varepsilon})$ exists for incremental or decremental $(4/3-\varepsilon')$-approximating the diameter of an unweighted graph. We also show a slightly stronger bound if node additions are allowed. [...]

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. [...]

In the incremental cycle detection problem, edges are added to a directed graph (initially empty), and the algorithm has to report the presence of the first cycle, once it is formed. A closely related problem is the incremental topological sort problem, where edges are added to an acyclic graph, and the algorithm is required to maintain a valid topological ordering. Since these problems arise naturally in many applications such as scheduling tasks, pointer analysis, and circuit evaluation, they have been studied extensively in the last three decades. Motivated by the fact that in many of these applications, the presence of a cycle is not fatal, we study a generalization of these problems, incremental maintenance of strongly connected components (incremental SCC). Several incremental algorithms in the literature which do cycle detection and topological sort in directed acyclic graphs, such as those by [Michael A. Bender et al., 2016] and [Haeupler et al., 2012], also generalize to maintain strongly connected components and their topological sort in general directed graphs. The algorithms of [Haeupler et al., 2012] and [Michael A. Bender et al., 2016] have a total update time of O(m^{3/2}) and O(m⋅ min{m^{1/2},n^{2/3}}) respectively, and this is the state of the art for incremental SCC. But the most recent algorithms for incremental cycle detection and topological sort ([Bernstein and Chechik, 2018] and [Bhattacharya and Kulkarni, 2020]), which yield total (randomized) update time Õ(min{m^{4/3}, n²}), do not extend to incremental SCC. Thus, there is a gap between the best known algorithms for these two closely related problems. In this paper, we bridge this gap by extending the framework of [Bhattacharya and Kulkarni, 2020] to general directed graphs. More concretely, we give a Las Vegas algorithm for incremental SCCs with an expected total update time of Õ(m^{4/3}). A key ingredient in the algorithm of [Bhattacharya and Kulkarni, 2020] is a structural theorem (first introduced in [Bernstein and Chechik, 2018]) that bounds the number of "equivalent" vertices. Unfortunately, this theorem only applies to DAGs. We show a natural way to extend this structural theorem to general directed graphs, and along the way we develop a significantly simpler and more intuitive proof of this theorem.

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.

We introduce a new framework for computing approximate maximum weight matchings. Our primary focus is on the fully dynamic setting, where there is a large gap between the guarantees of the best known algorithms for computing weighted and unweighted matchings. Indeed, almost all current weighted matching algorithms that reduce to the unweighted problem lose a factor of two in the approximation ratio. In contrast, in other sublinear models such as the distributed and streaming models, recent work has largely closed this weighted/unweighted gap.

Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability. In this article, we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem. (1) For dynamic spanner, the only known o ( n ) worst-case bounds were O ( n 3/4 ) high-probability worst-case update time for maintaining a 3-spanner and O ( n 5/9 ) for maintaining a 5-spanner. We give a O (1) k log 3 ( n ) high-probability worst-case time bound for maintaining a ( 2k-1 )-spanner, which yields the first worst-case polylog update time for all constant k . (All the results above maintain the optimal tradeoff of stretch 2k-1 and Õ( n 1+1/k ) edges.) (2) For dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O (log 5 ( n )) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2+ϵ)-approximate, and hence not maximal. Our results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: An algorithm is said to have worst-case expected update time ɑ if for every update σ, the expected time to process σ is at most ɑ. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: A worst-case expected update time of O(1) still allows for the possibility that every 1/ f(n) updates requires ϴ ( f(n) ) time to process, for arbitrarily high f(n) . In this article, we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: The query time remains the same, while the update time increases by a factor of O (log 2(n) ). Thus, we achieve our results in two steps: (1) First, we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times. (2) Then, we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms.

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.

The matching problem in the online setting models the following situation: we are given a set of servers in advance, the clients arrive one at a time, and each client has edges to some of the servers. Each client must be matched to some incident server upon arrival (or left unmatched) and the algorithm is not allowed to reverse its decisions. Due to this no-reversal restriction, we are not able to guarantee an exact maximum matching in this model, only an approximate one. Therefore, it is natural to study a different setting, where the top priority is to match as many clients as possible, and changes to the matching are possible but expensive. Formally, the goal is to always maintain a maximum matching while minimizing the number of changes made to the matching (denoted the recourse). This model is called the online model with recourse, and has been studied extensively over the past few years. For the specific problem of matching, the focus has been on vertex-arrival model, where clients arrive one at a time with all their edges. A recent result of Bernstein et al. [Bernstein et al., 2019] gives an upper bound of O (nlog² n) recourse for the case of general bipartite graphs. For trees the best known bound is O(nlog n) recourse, due to Bosek et al. [Bosek et al., 2018]. These are nearly tight, as a lower bound of Ω(nlog n) is known. In this paper, we consider the more general model where all the vertices are known in advance, but the edges of the graph are revealed one at a time. Even for the simple case where the graph is a path, there is a lower bound of Ω(n²). Therefore, we instead consider the natural relaxation where the graph is worst-case, but the edges are revealed in a random order. This relaxation is motivated by the fact that in many related models, such as the streaming setting or the standard online setting without recourse, faster algorithms have been obtained for the matching problem when the input comes in a random order. Our results are as follows: - Our main result is that for the case of general (non-bipartite) graphs, the problem with random edge arrivals is almost as hard as in the adversarial setting: we show a family of graphs for which the expected recourse is Ω(n²/log n). - We show that for some special cases of graphs, random arrival is significantly easier. For the case of trees, we get an upper bound of O(nlog²n) on the expected recourse. For the case of paths, this upper bound is O(nlog n). We also show that the latter bound is tight, i.e. that the expected recourse is at least Ω(nlog n).

We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, the edges of the input graph G = (V,E) are given as a stream e₁, …, e_m, and the algorithm is allowed to make a single pass over this stream while using O(n polylog(n)) space (m = |E| and n = |V|). If the order of edges is adversarial, a simple single-pass greedy algorithm yields a 1/2-approximation in O(n) space; achieving a better approximation in adversarial streams remains an elusive open question. A line of recent work shows that one can improve upon the 1/2-approximation if the edges of the stream arrive in a random order. The state of the art for this model is two-fold: Assadi et al. [SODA 2019] show how to compute a 2/3(∼.66)-approximate matching, but the space requirement is O(n^1.5 polylog(n)). Very recently, Farhadi et al. [SODA 2020] presented an algorithm with the desired space usage of O(n polylog(n)), but a worse approximation ratio of 6/11(∼.545), or 3/5(=.6) in bipartite graphs. In this paper, we present an algorithm that computes a 2/3(∼.66)-approximate matching using only O(n log(n)) space, improving upon both results above. We also note that for adversarial streams, a lower bound of Kapralov [SODA 2013] shows that any algorithm that achieves a 1-1/e(∼.63)-approximation requires (n^{1+Ω(1/log log(n))}) space. Our result for random-order streams is the first to go beyond the adversarial-order lower bound, thus establishing that computing a maximum matching is provably easier in random-order streams.

In the load balancing problem, the input is an $n$-vertex bipartite graph $G = (C \cup S, E)$ and a positive weight for each client $c \in C$. The algorithm must assign each client $c \in C$ to an adjacent server $s \in S$. The load of a server is then the weighted sum of all the clients assigned to it, and the goal is to compute an assignment that minimizes some function of the server loads, typically either the maximum server load (i.e., the $\ell_{\infty}$-norm) or the $\ell_p$-norm of the server loads. We study load balancing in the distributed setting. There are two existing results in the CONGEST model. Czygrinow et al. [DISC 2012] showed a 2-approximation for unweighted clients with round-complexity $O(Δ^5)$, where $Δ$ is the maximum degree of the input graph. Halldórsson et al. [SPAA 2015] showed an $O(\log{n}/\log\log{n})$-approximation for unweighted clients and $O(\log^2\!{n}/\log\log{n})$-approximation for weighted clients with round-complexity polylog$(n)$. In this paper, we show the first distributed algorithms to compute an $O(1)$-approximation to the load balancing problem in polylog$(n)$ rounds. In the CONGEST model, we give an $O(1)$-approximation algorithm in polylog$(n)$ rounds for unweighted clients. For weighted clients, the approximation ratio is $O(\log{n})$. In the less constrained LOCAL model, we give an $O(1)$-approximation algorithm for weighted clients in polylog$(n)$ rounds. Our approach also has implications for the standard sequential setting in which we obtain the first $O(1)$-approximation for this problem that runs in near-linear time. A 2-approximation is already known, but it requires solving a linear program and is hence much slower. Finally, we note that all of our results simultaneously approximate all $\ell_p$-norms, including the $\ell_{\infty}$-norm.

There is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex cover, on massive graphs. For massive inputs, several different computational models have been introduced, including the streaming model, the distributed communication model, and the massively parallel computation (MPC) model that is a common abstraction of MapReduce-style computation. In each model, algorithms are analyzed in terms of resources such as space used or rounds of communication needed, in addition to the more traditional approximation ratio. In this paper, we give a single unified approach that yields better approximation algorithms for matching and vertex cover in all these models. The highlights include: The first one pass, significantly-better-than-2-approximation for matching in random arrival streams that uses subquadratic space, namely a (1.5 + ε)-approximation streaming algorithm that uses Õ(n15) space for constant ε > 0. The first 2-round, better-than-2-approximation for matching in the MPC model that uses subquadratic space per machine, namely a (1.5 + ε)-approximation algorithm with memory per machine for constant ε > 0. By building on our unified approach, we further develop parallel algorithms in the MPC model that give a (1+∊)-approximation to matching and an O(1)-approximation to vertex cover in only O(log log n) MPC rounds and O(n/polylog(n)) memory per machine. These results settle multiple open questions posed by Czumaj et al. [STOC 2018]. We obtain our results by a novel combination of two previously disjoint set of techniques, namely randomized composable coresets and edge degree constrained subgraphs (EDCS). We significantly extend the power of these techniques and prove several new structural results. For example, we show that an EDCS is a sparse certificate for large matchings and small vertex covers that is quite robust to sampling and composition.

Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas), and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability. In this paper we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem. 1. For dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner, and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3(n) high-probability worst-case time bound for maintaining a (2k – 1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k – 1 and Õ(n1+1/k) edges.) 2. For dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2 + ∊)-approximate, and hence not maximal. Our results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: an algorithm is said to have worst-case expected update time α if for every update σ, the expected time to process σ is at most α. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: a worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires Θ(f(n)) time to process, for arbitrarily high f(n). In this paper we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: the query time remains the same, while the update time increases by a factor of O(log2(n)). Thus we achieve our results in two steps: (1) First we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times. (2) Then we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms.

In the distributed all-pairs shortest paths problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity). The problem admits (1+o(1))-approximation Θ(n)-time algorithm and a nearly-tight Ω(n) lower bound [Nanongkai, STOC’14; Lenzen and Patt-Shamir PODC’15]. For the exact case, Elkin [STOC’17] presented an O(n5/3 log2/3 n) time bound, which was later improved to Õ(n5/4) in [Huang, Nanongkai, Saranurak FOCS’17].It was shown that any super-linear lower bound (in n) requires a new technique [Censor-Hillel, Khoury, Paz, DISC’17], but otherwise it remained widely open whether there exists a Õ(n)-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) Õ(n)-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous Õ(n5/4) bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous Õ(n5/4) bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in {1, 2, ... poly(n)}). The previously best algorithm for this more difficult setting required Õ(n3/2) time [Agarwal and Ramachandran, ArXiv’18] (this can be improved to Õ(n4/3) if one allows bidirectional communication).

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.

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one-by-one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O (log 2 n ) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω (log n ) lower bound. The previous best strategy known achieved amortized O (√ n ) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better than the trivial O ( n ) bound was known except in special cases. Our analysis immediately implies the same upper bound of O (log 2 n ) reassignments for the capacitated assignment problem, where each vertex on the static side of the bipartition is initialized with the capacity to serve a number of vertices. We also analyze the problem of minimizing the maximum server load. We show that if the final graph has maximum server load L , then the SAP protocol makes amortized O (min { L log 2 n , √ n log n }) reassignments. We also show that this is close to tight, because Ω (min { L , √ n }) reassignments can be necessary.

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$.

In the distributed all-pairs shortest paths problem, every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity). The problem admits a $(1+o(1))$-approximation $\tilde\Theta(n)$-time algorithm and a nearly tight $\tilde \Omega(n)$ lower bound [D. Nanongkai, STOC'14, ACM, New York, 2014, pp. 565--573; C. Lenzen and B. Patt-Shamir, PODC'15, ACM, New York, 2015, pp. 153--162]. ($\tilde \Theta$, $\tilde O$ and $\tilde \Omega$ hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios (C. Lenzen and D. Peleg, PODC, ACM, New York, 2013, pp. 375--382; S. Holzer and R. Wattenofer, PODC, ACM, New York, 2012, pp. 355--364; D. Peleg, L. Roditty, and E. Tal, ICALP, Springer, Berlin, 2012, pp. 660--672; D. Nanongkai, STOC, ACM, New York, 2014, pp. 565--573--672). For the exact case, Elkin [STOC'17, ACM, New York, 2017, pp. 757--790] presented an $O(n^{5/3} \log^{2/3} n)$ time bound, which was later improved to $\tilde O(n^{5/4})$ [C.-C. Huang, D. Nanongkai, T. Saranurak, FOCS'17, IEEE Computer Society, Los Alamitos, CA, 2017, pp. 168--179]. It was shown that any superlinear lower bound (in $n$) requires a new technique [K. Censor-Hillel, S. Khoury, A. Paz, DISC'17, LIPIcs Leibniz Int. Proc. Inform., Vol. 91, Schloss-Dagstuhl, Wadern, Germany, 2017, 10], but otherwise it remained widely open whether there exists a $\tilde O(n)$-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) $\tilde O(n)$-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous $\tilde O(n^{5/4})$ bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous $\tilde O(n^{5/4})$ bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in $\{1, 2, \ldots, \operatorname{poly}(n)\}$). As far as we know, ours is the first $o(n^2)$ algorithm that only requires unidirectional communication. For arbitrary weights, the previous state-of-the-art required $\tilde O(n^{4/3})$ time [U. Agarwal and V. Ramachandran, IPDPS 2019, IEEE Computer Society, Los Alamitos, CA, 2019, and SPAA 2020, ACM, New York, 2020, pp. 11--21]. Our algorithm is extremely simple and relies on a new technique called random filtered broadcast. Given any sets of nodes $A,B\subseteq V$ and assuming that every $b \in B$ knows all distances from nodes in $A$, and every node $v \in V$ knows all distances from nodes in $B$, we want every $v\in V$ to know ${\sf DistThrough}_B(a,v) = \min_{b\in B} {dist}(a,b) + {\sf dist}(b,v)$ for every $a\in A$. Previous works typically solve this problem by broadcasting all knowledge of every $b\in B$, causing superlinear edge congestion and time. We show a randomized algorithm that can reduce edge congestions and thus solve this problem in $\tilde O(n)$ expected time.

Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. In this paper we propose and study a new framework contracting edges of a graph (merging vertices into supervertices) with the goal of preserving pairwise distances as accurately as possible. Formally, given an edge-weighted graph, the contraction should guarantee that for any two vertices at distance $d$, the corresponding supervertices remain at distance at least $\varphi(d)$ in the contracted graph, where $\varphi$ is a tolerance function bounding the permitted distance distortion. We present a comprehensive picture of the algorithmic complexity of the contraction problem for affine tolerance functions $\varphi(x)=x/\alpha-\beta$, where $\alpha\geq 1$ and $\beta\geq 0$ are arbitrary real-valued parameters. Specifically, we present polynomial-time algorithms for trees as well as hardness and inapproximability results for different graph classes, precisely separating easy and hard cases. Further we analyze the asymptotic behavior of contractions, and find efficient algorithms to compute (nonoptimal) contractions despite our hardness results.

Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. \nIn this paper we propose and study a new framework contracting edges of a graph (merging vertices into super-vertices) with the goal of preserving pairwise distances as accurately as possible. \nFormally, given an edge-weighted graph, the contraction should guarantee that for any two vertices at distance d, the corresponding super-vertices remain at distance at least \\varphi(d) in the contracted graph, where \\varphi is a tolerance function bounding the permitted distance distortion. \nWe present a comprehensive picture of the algorithmic complexity of the contraction problem for affine tolerance functions \\varphi(x)=x/\\alpha-\\beta, where \\alpha \\geq 1 and \\beta \\geq 0 are arbitrary real-valued parameters. \nSpecifically, we present polynomial-time algorithms for trees as well as hardness and inapproximability results for different graph classes, precisely separating easy and hard cases. \nFurther we analyze the asymptotic behavior of the size of contractions, and find efficient algorithms to compute (non-optimal) contractions despite our hardness results.

In the incremental cycle detection problem edges are inserted to a directed graph (initially empty) and the algorithm has to report once a directed cycle is formed in the graph. A closely related problem to the incremental cycle detection is that of the incremental topological sort problem, in which edges are inserted to an acyclic graph and the algorithm has to maintain a valid topological sort on the vertices at all times. Both incremental cycle detection and incremental topological sort have a long history. The state of the art is a recent breakthrough of Bender, Fineman, Gilbert and Tarjan [TALG 2016], with two different algorithms with respective total update times of Õ(n2) and O(m · min{m1/2, n2/3}). The two algorithms work for both incremental cycle detection and incremental topological sort. In this paper we introduce a novel technique that allows us to improve upon the state of the art for a wide range of graph sparsity. Our algorithms has a total expected update time of for both the incremental cycle detection and the topological sort problems.

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(log n) lower bound. The previous best strategy known achieved amortized replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better than then trivial bound was known except in special cases. Our analysis immediately implies the same upper bound of reassignments for the capacitated assignment problem, where each vertex on the static side of the bipartition is initialized with the capacity to serve a number of vertices. We also analyze the problem of minimizing the maximum server load. We show that if the final graph has maximum server load L, then the SAP protocol makes amortized reassignments. We also show that this is close to tight because reassignments can be necessary.

In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest distances between s and all other nodes in G under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem in unweighted graphs with only O(mn) total update time over all edge deletions. Their classic algorithm was the state of the art for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. The first improvement over the Even-Shiloach algorithm was given by Bernstein and Roditty [SODA 2011], who for the case of an unweighted and undirected graph presented a (1+epsilon)-approximate algorithm with constant query time and a total update time of O(n^{2+o(1)}). This work triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a (1+epsilon)-approximate algorithm for undirected weighted graphs whose total update time is near linear: O(m^{1+o(1)} log(W)), where W is the ratio of the heaviest to the lightest edge weight in the graph. In this paper they posed as a major open problem the question of derandomizing their result. Until very recently, all known improvements over the Even-Shiloach algorithm were randomized and required the assumption of a non-adaptive adversary. In STOC 2016, Bernstein and Chechik showed the first deterministic algorithm to go beyond O(mn) total update time: the algorithm is also (1+\epsilon)-approximate, and has total update time \tilde{O}(n^2). In SODA 2017, the same authors presented an algorithm with total update time \tilde{O}(mn^{3/4}). However, both algorithms are restricted to undirected, unweighted graphs. We present the first deterministic algorithm for weighted undirected graphs to go beyond the O(mn) bound. The total update time is \tilde{O}(n^2 \log(W)).

This paper investigates the task of load balancing where the objective function is to minimize the p-norm of loads, for p\geq 1, in both static and incremental settings. We consider two closely related load balancing problems. In the bipartite matching problem we are given a bipartite graph G=(C\cup S, E) and the goal is to assign each client c\in C to a server s\in S so that the p-norm of assignment loads on S is minimized. In the graph orientation problem the goal is to orient (direct) the edges of a given undirected graph while minimizing the p-norm of the out-degrees. The graph orientation problem is a special case of the bipartite matching problem, but less complex, which leads to simpler algorithms. For the graph orientation problem we show that the celebrated Chiba-Nishizeki peeling algorithm provides a simple linear time load balancing scheme whose output is an orientation that is 2-competitive, in a p-norm sense, for all p\geq 1. For the bipartite matching problem we first provide an offline algorithm that computes an optimal assignment. We then extend this solution to the online bipartite matching problem with reassignments, where vertices from C arrive in an online fashion together with their corresponding edges, and we are allowed to reassign an amortized O(1) vertices from C each time a new vertex arrives. In this online scenario we show how to maintain a single assignment that is 8-competitive, in a p-norm sense, for all p\geq 1.

In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions. (Our algorithm can also be modified to work in the incremental setting, where the graph is initially empty and subject to a sequence of online adversarial edge insertions.) In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem with only O (mn) total update time over all edge deletions. Later papers presented conditional lower bounds showing that O(mn) is optimal up to log factors. In SODA 2011, Bernstein and Roditty showed how to bypass these lower bounds and improve upon the Even and Shiloach O(mn) total update time bound by allowing a (1 + ∊) approximation. This triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a (1 + ∊)-approximate algorithm whose total update time is near linear: However, every single one of these improvements over the Even-Shiloach algorithm was randomized and assumed a non-adaptive adversary. This additional assumption meant that the algorithms were not suitable for certain settings and could not be used as a black box data structure. Very recently Bernstein and Chechik presented in STOC 2016 the first deterministic improvement over Even and Shiloach, that did not rely on randomization or assumptions about the adversary: in an undirected unweighted graph the algorithm maintains (1+ ∊)-approximate distances and has total update time O(n2). In this paper, we present a new deterministic algorithm for the problem with total update time Õ(n1.25√m) = Õ (mn3/4): it returns a (1 + ∊) approximation, and is limited to undirected unweighted graphs. Although this result is still far from matching the randomized near-linear total update time, it presents important progress towards that direction, because unlike the STOC 2016 Õ (n2) algorithm it beats the Even and Shiloach Õ (mn) bound for all graphs, not just sufficientl6y dense ones. In particular, the Õ (n2) algorithm relied entirely on a new sparsification technique, and so could not hope to yield an improvement for sparse graphs. We present the first deterministic improvement for sparse graphs by significantly extending some of the ideas from the Õ (n2) algorithm and combining them with the hop-set technique used in several earlier dynamic shortest path papers. Also, because decremental single source shortest paths is often used as a building block for fully dynamic all pairs shortest paths, using our new algorithm as a black box yields new deterministic algorithms for fully dynamic approximate all pairs shortest paths.

Maximum cardinality matching is a fundamental algorithmic problem with many algorithms and applications. The fully dynamic version, in which edges are inserted and deleted over time has also been the subject of much attention. Existing algorithms for dynamic matching (in general n-vertex m-edge graphs) fall into two groups: there are fast (mostly randomized) algorithms that achieve a 2-approximation or worse, and there are slow algorithms with update time that achieve a better-than-2 approximation. Thus the obvious question is whether we can design an algorithm that achieves a tradeoff between these two: a update time and a better-than-2 approximation simultaneously. We answer this question in the affirmative. Previously, such bounds were only known for the special case of bipartite graphs. Our main result is a fully dynamic deterministic algorithm that maintains a (3/2 + ∊)-approximation in amortized update time O(m1/4∊–2.5). In addition to achieving the trade-off described above, our algorithm manages to be polynomially faster than all existing deterministic algorithms (excluding an existing log n-approximation of Onak and Rubinfeld), while still maintaining a better-than-2 approximation. We also give stronger results for graphs whose arboricity is at most α. We show how to maintain a (1 + ∊)-approximate fractional matching or a (3/2 + ∊)-approximate integral matching in worst-case time O(α(α + log n)) for constant ∊. When the arboricity is constant, this bound is O(log n) and when the arboricity is polylogarithmic the update time is also polylogarithmic. Previous results for small arboricity non-bipartite graphs could only maintain a maximal matching (2-approximation). We maintain the approximate matching without explicitly using augmenting paths. We define an intermediate graph, called an EDCS and show that the EDCS H contains a large matching, and show how to maintain an EDCS in G. The EDCS was used in previous works on bipartite graphs, however the details and proofs are completely different in general graphs. The algorithm for bipartite graphs relies on ideas from flows and cuts to non-constructively prove the existence of a good matching in H, but these ideas do not seem to extend to non-bipartite graphs. In this paper we instead explicitly construct a large fractional matching in H. In some cases we can guarantee that this fractional matching is γ-restricted, which means that it only uses values either in the range [0, γ] or 1. We then combine this matching with a new structural property of maximum matchings in non-bipartite graphs, which is analogous to the cut induced by maximum matchings in bipartite graphs.

In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions.

We present an improved algorithm for maintaining all-pairs $(1 + \epsilon)$ approximate shortest paths under deletions and weight-increases. The previous state of the art for this problem is total update time $\widetilde{O}(n^2\sqrt{m}/\epsilon)$ over all updates for directed unweighted graphs [S. Baswana, R. Hariharan, and S. Sen, J. Algorithms, 62 (2007), pp. 74--92], and $\widetilde{O}(mn/\epsilon)$ for undirected unweighted graphs [L. Roditty and U. Zwick, in Proceedings of the 45th FOCS, Rome, Italy, 2004, pp. 499--508]. Both algorithms are randomized and have constant query time. Very recently, Henzinger, Krinninger, and Nanongkai presented a deterministic version of the latter algorithm [M. Henzinger, S. Krinninger, and D. Nanongkai, in IEEE FOCS, 2013, pp. 538--547]. Note that $\widetilde{O}(mn)$ is a natural barrier because even with a $(1 + \epsilon)$ approximation, there is no $o(mn)$ combinatorial algorithm for the static all-pairs shortest path problem. Our algorithm works on directed weighted graphs and has total (randomized) update time $\widetilde{O}(mn\log R/\epsilon)$ where $R$ is the ratio of the largest edge weight to appear at any point in the update sequence to the smallest such weight. (As with previous algorithms, our query time is constant.) Technically, the running time is $\widetilde{O}(mn\log R/\epsilon) + O(\Delta)$, where $\Delta$ is the total number of updates; the same $O(\Delta)$ term is also implicitly present in all other algorithms for the problem, since a constant time per update is clearly unavoidable. Note that $\log R = O(\log(n))$ as long as weights are polynomial in $n$; thus, we effectively expand the $\widetilde{O}(mn/\epsilon)$ total update time bound from undirected unweighted graphs to directed graphs with polynomial weights. This is in fact the first nontrivial algorithm for decremental all-pairs shortest paths that works on weighted graphs (previous algorithms could only handle small integer weights). By a well-known reduction from decremental algorithms to fully dynamic ones [M. Henzinger and V. King, in Proceedings of the 36th FOCS, Milwaukee, WI, 1995, pp. 664--672], our improved decremental algorithm leads to improved query-update trade-offs for fully dynamic $(1 + \epsilon)$ approximate all-pairs shortest paths (APSP) algorithms in directed graphs.

We present an improved algorithm for maintaining all-pairs 1 + ε approximate shortest paths under deletions and weight-increases. The previous state of the art for this problem was total update time ~O (n2√m/ε) for directed, unweighted graphs [2], and ~O(mn/ε) for undirected, unweighted graphs [12]. Both algorithms were randomized and had constant query time. Note that ~O(mn) is a natural barrier because even with a (1 + ε) approximation, there is no o(mn) combinatorial algorithm for the static all-pairs shortest path problem. Our algorithm works on directed, weighted graphs and has total (randomized) update time ~O (mn log(R)/ε) where R is the ratio of the largest edge weight ever seen in the graph, to the smallest such weight (our query time is constant). Note that log(R) = O(log(n)) as long as weights are polynomial in n. Although ~O(mn log(R)/ε) is the total time over all updates, our algorithm also requires a clearly unavoidable constant time per update. Thus, we effectively expand the ~O(mn) total update time bound from undirected, unweighted graphs to directed graphs with polynomial weights. This is in fact the first non-trivial algorithm for decremental all-pairs shortest paths that works on weighted graphs (previous algorithms could only handle small integer weights).

We present a significantly faster algorithm for the restricted shortest path problem, in which we are given two vertices s, t, and the goal is to find the shortest path that is subject to a side constraint. More formally, rather than just having a single weight, each edge has two weights: a cost-weight, and a delay-weight. We are given a threshold T which corresponds to the maximum delay we can afford, and the goal is to find the s − t path that minimizes total cost while still having delay-length at most T.

We present the first dynamic shortest paths algorithms that make any progress beyond a longstanding O(n) update time barrier (while maintaining a reasonable query time), although it is only progress for not-too-sparse graphs. In particular, we obtain new decremental algorithms for two approximate shortest-path problems in unweighted, undirected graphs. Both algorithms are randomized (Las Vegas). Given a source s, we present an algorithm that maintains (1 + ∊)-approximate shortest paths from s with an expected total update time of over all deletions (so the amortized time is about . The worst-case query time is constant. The best previous result goes back three decades to Even and Shiloach [16] and Dinitz [12]. They show how to decrementally maintain an exact shortest path tree with a total update time of O(mn) (amortized update time O(n)). Roditty and Zwick [22] have shown that O(mn) is actually optimal for exact paths (barring a better combinatorial algorithm for boolean matrix multiplication), unless we are willing to settle for a Ω(n) query time. In fact, until now, even approximate dynamic algorithms were not able to go beyond O(mn). For any fixed integer k ≥ 2, we present an algorithm that decrementally maintains a distance oracle (for all pairs shortest distances) with a total expected update time of (amortized update time about . The space requirement is only O(m + n1+1/k), the stretch of the returned distances is at most 2k − 1 + ∊, and the worst-case query time is O(1). The best previous result of Roditty and Zwick [21] had a total update time of and a stretch of 2k − 1. Note that our algorithm implicitly solves the decremental all-pairs shortest path problem with the same bounds; the best previous approximation algorithm of Roditty and Zwick [21] returned (1 + ∊) approximate distances, but used O(n2) space, and required total update time. As with the previous problem, our algorithm is the first to make progress beyond the O(mn) total update time barrier while maintaining a small query time. We present a general framework for accelerating decremental algorithms. In particular, our main idea is to run existing decremental algorithms on a sparse subgraph (such as a spanner or emulator) of the graph rather than on the original graph G. Although this is a common approach for static approximate shortest-path problems, it has never been used in a decremental setting because maintaining the subgraph H as edges are being deleted from G might require inserting edges into H, thus ruining the “decrementality” of the setting. We overcome this by presenting an emulator whose maintenance only requires a limited number of well-behaved insertions. In other words, we present a general technique for running decremental algorithms on a sparse subgraph of the graph. Once our framework is in place, applying it to any particular decremental algorithm only requires trivial modifications; most of the work consists of showing that these algorithms as they are still work in our restricted fully dynamic setting, where we encounter not just arbitrary deletions (as in the original setting), but also restricted insertions.

Let G = (V, E) be a directed graph with positive edge weights, let s, t be two specified vertices in this graph, and let π(s, t) be the shortest path between them. In the replacement paths problem we want to compute, for every edge e on π(s, t), the shortest path from s to t that avoids e. The naive solution to this problem would be to remove each edge e, one at a time, and compute the shortest s – t path each time; this yields a running time of O(mn + n log n). Gotthilf and Lewenstein [8] recently improved this to O(mn + n2 log log n), but no o(mn) algorithms are known. We present the first approximation algorithm for replacement paths in directed graphs with positive edge weights. Given any ε ∊ [0, 1), our algorithm returns (1 + ε)-approximate replacement paths in time, where C is the largest edge weight in the graph and c is the smallest weight. We also present an even faster (1 + ε) approximate algorithm for the simpler problem of approximating the k shortest simple s – t paths in a directed graph with positive edge weights. That is, our algorithm outputs k different simple s – t paths, where the kth path we output is a (1 + ε) approximation to the actual kth shortest simple s – t path. The running time of our algorithm is . The fastest exact algorithm for this problem has a running time of [8]. The previous best approximation algorithm was developed by Roditty [15]; it has a stretch of 3/2 and a running time of (it does not work for replacement paths). Note that all of our running times are nearly optimal except for the O(log(nC/c)) factor in the replacements paths algorithm. Also, our algorithm can solve the variant of approximate replacement paths where we avoid vertices instead of edges.

For any fixed 1 > ¿ > 0 we present a fully dynamic algorithm for maintaining (2 + ¿)-approximate all-pairs shortest paths in undirected graphs with positive edge weights. We use a randomized (Las Vegas) update algorithm (but a deterministic query procedure), so the time given is the expected amortized update time. Our query time O(log log log n). The update time is O¿(mnO(1/¿(log n))log (nR)), where R is the ratio between the heaviest and the lightest edge weight in the graph (so R = 1 in unweighted graphs). Unfortunately, the update time does have the drawback of a super-polynomial dependence on e. it grows as (3/¿)(¿(log n/log(3/¿))) = n(¿(log(3/¿)/log n)). Our algorithm has a significantly faster update time than any other algorithm with sub-polynomial query time. For exact distances, the state of the art algorithm has an update time of O¿(n2). For approximate distances, the best previous algorithm has a O(kmn1/k) update time and returns (2 k - 1) stretch paths. Thus, it needs an update time of O(m¿(n)) to get close to our approximation, and it has to return O(¿(log n)) approximate distances to match our update time.

We present an improved oracle for the distance sensitivity problem. The goal is to preprocess a directed graph G = (V,E) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from x to y that does not go through some failed vertex or edge f. The previous best algorithm produces an oracle of size ~O(n2) that has an O(1) query time, and an ~O(n2√m) construction time. It was a randomized Monte Carlo algorithm that worked with high probability. Our oracle also has a constant query time and an ~O(n2) space requirement, but it has an improved construction time of ~O(mn), and it is deterministic. Note that O(1) query, O(n2) space, and O(mn) construction time is also the best known bound (up to logarithmic factors) for the simpler problem of finding all pairs shortest paths in a weighted, directed graph. Thus, barring improved solutions to the all pairs shortest path problem, our oracle is optimal up to logarithmic factors.