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 present the first polynomial-time algorithm for computing a near-optimal flow-expander decomposition. Given a graph G and a parameter ϕ, our algorithm removes at most a ϕlog^{1+o(1)}n fraction of edges so that every remaining connected component is a ϕ-flow-expander (a stronger guarantee than being a ϕ-cut-expander). This achieves overhead log^{1+o(1)}n, nearly matching the Ω(log n) graph-theoretic lower bound that already holds for cut-expander decompositions, up to a log^{o(1)}n factor. Prior polynomial-time algorithms required removing O(ϕlog^{1.5}n) and O(ϕlog²n) fractions of edges to guarantee ϕ-cut-expander and ϕ-flow-expander components, respectively.

We study connectivity oracle under vertex failures, one of the most fundamental graph data structures with many applications. We provide a new deterministic connectivity oracle that handles update in O(k⁶) time and answers query in O(k) time, while using 2^O(k²) n + O(k²n α_c(n)) space and k^O(k²) n + O(m + k³ n log² n + k⁶n log n) preprocessing time. Although some previous works achieve k² ⋅ n^o(1) update time and O(k) query time [Long and Saranurak, 2022; Yaowei Long and Yunfan Wang, 2024], the update time is still n-dependent, while oracles that have n-independent update and query times [Michal Pilipczuk et al., 2022; Jan van den Brand and Thatchaphol Saranurak, 2019] cannot achieve optimal O(k) query time [Monika Henzinger et al., 2015] and often have Ω(n²) space and processing time. Our solution would be the first vertex-failure connectivity oracle that achieves O(k) query time with update time completely independent of n, while improving space usage and having competitive preprocessing 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 design efficient deterministic algorithms for finding short edge-disjoint paths in expanders. Specifically, given an \(n\)-vertex \(m\)-edge expander \(G\) of conductance \(\phi\) and minimum degree \(\delta\), and a set of pairs \(\{(s_i,t_i)\}_i\) such that each vertex appears in at most \(k\) pairs, our algorithm deterministically computes a set of edge-disjoint paths from \(s_i\) to \(t_i\), one for every \(i\): (1) each of length at most \(18 \log(n)/\phi\) and in \(mn^{1+o(1)} \min\{k,\phi^{-1}\}\) total time, assuming \(\phi^3 \delta \ge (35 \log n)^3 k\), or (2) each of length at most \(n^{o(1)}/\phi\) and in total \(m^{1+o(1)}\) time, assuming \(\phi^3 \delta \ge n^{o(1)} k\). Before our work, deterministic polynomial-time algorithms were known only for expanders with constant conductance and were significantly slower. To obtain our result, we give an almost-linear time algorithm for hypergraph perfect matching under generalizations of Hall-type conditions (Haxell 1995), a powerful framework with applications in various settings, which until now has only admitted large polynomial-time algorithms (Annamalai 2018).

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.

We present the first deterministic nearly-linear time algorithm for single-source shortest paths with negative edge weights on directed graphs: given a directed graph G with n vertices, m edges whose weights are integer in {−W,…,W}, our algorithm either computes all distances from a source s or reports a negative cycle in time O(m)· log(nW) time.

We show that every directed graph G with n vertices and m edges admits a directed acyclic graph (DAG) with m1+o(1) edges, called a DAG projection, that can either (1+1/polylog (n))-approximate distances between all pairs of vertices (s,t) in G, or no(1)-approximate maximum flow between all pairs of vertex subsets (S,T) in G. Previous similar results suffer a Ω(logn) approximation factor for distances [Assadi, Hoppenworth, Wein, STOC’25] [Filtser, SODA’26] and, for maximum flow, no prior result of this type is known.

A fault-tolerant distance labeling scheme assigns a label to each vertex and edge of an undirected weighted graph G with n vertices so that, for any edge set F of size |F| ≤ f, one can approximate the distance between p and q in G ∖ F by reading only the labels of F ∪ {p,q}.

Abstract. A [Formula: see text]- vertex connectivity oracle for an undirected graph [Formula: see text] is a data structure that, given [Formula: see text], reports [Formula: see text], where [Formula: see text] is the pairwise vertex connectivity between [Formula: see text]. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov [ Inform. Process. Lett., 112 (2012), pp. 39–43] produced a data structure of [Formula: see text] words, which can even be encoded as a [Formula: see text]-bit labeling scheme, that can answer vertex connectivity queries in [Formula: see text] time. The construction time is polynomial but unspecified. In this paper, we address the top three complexity measures. (1) Space: We prove that any [Formula: see text]-vertex connectivity oracle requires [Formula: see text] bits of space for any [Formula: see text]. This proves that the Iszak–Nutov data structure is optimal up to polylogarithmic factors for every [Formula: see text] and that the sparsifiers of Nagamochi and Ibaraki [ Algorithmica, 7 (1992), pp. 583–596] are optimal compression schemes for [Formula: see text]-vertex connectivity up to a logarithmic factor. In particular, whereas all edge connectivities can be efficiently compressed (as a weighted [Formula: see text]-edge Gomory–Hu tree), vertex connectivity admits no asymptotic compression: [Formula: see text] bits are necessary. We design a variation on Izsak and Nutov’s data structure that uses [Formula: see text] words of space. (2) Query time: We answer queries in [Formula: see text] time, improving on the [Formula: see text] time bound of Izsak and Nutov [ Inform. Process. Lett., 112 (2012), pp. 39–43]. The main idea is to build instances of [Formula: see text] data structures, with additional structure based on affine planes. This structure allows for query time that is linear in the output size, which evades some conditional lower bounds that are polynomial in the query set sizes [ 42 , 51 ]. (3) Construction time: Our data structure can be constructed in the time of [Formula: see text] max-flow computations, namely, [Formula: see text] time, using the recent near-linear time flow algorithm of [ 13 ]. The main technical contribution here is a fast algorithm to compute a [Formula: see text]-approximate Gomory–Hu tree for element connectivity in the time of [Formula: see text] max-flow computations. Element connectivity is a notion that generalizes edge and vertex connectivity.

We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2022; Haeupler et al., 2024]. Along the way, we prove the multi-commodity maxflow-mincut theorems for length-constrained expansion in both directed and undirected vertex-capacitated graphs. Based on our decomposition, we build a length-constrained flow shortcut for undirected vertex-capacitated graphs, which roughly speaking is a set of edges and vertices added to the graph so that every multi-commodity flow demand can be routed with approximately the same vertex-congestion and length, but all flow paths only contain few edges. This generalizes the shortcut for undirected edge-capacitated graphs from [Bernhard Haeupler et al., 2024]. Length-constrained expander decomposition and flow shortcuts have been crucial in the recent algorithms in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2024; Haeupler et al., 2024]. Our work thus serves as a foundation to generalize these concepts to directed and vertex-capacitated graphs.

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

We present a parallel algorithm for computing ($1+ \epsilon$)-approximate min-cost flow on an undirected graph with m edges, where capacities and costs are assigned to both edges and vertices. Our algorithm achieves $\hat{O}(m)$ work and $\hat{O}(1)$ depth when $\epsilon\gt 1 / \operatorname{polylog}(m)$, making both the work and depth almost optimal, up to a subpolynomial factor. Previous algorithms with $\hat{O}(m)$ work required $\Omega(m)$ depth, even for special cases of min-cost flow with only edge capacities or max flow with vertex capacities. Our result generalizes prior almost-optimal parallel $(1+\epsilon)$-approximation algorithms for these special cases, including shortest paths [1]–[3] and max flow with only edge capacities [4], [5]. Our key technical contribution is the first construction of length-constrained flow shortcuts with $(1+\epsilon)$ length slack, $\hat{O}(1)$ congestion slack, and $\hat{O}(1)$ step bound. This provides a strict generalization of the influential concept of $(\hat{O}(1), \epsilon)$-hopsets [6], allowing for additional control over congestion. Previous lengthconstrained flow shortcuts [7] incur a large constant in the length slack, which would lead to a large approximation factor. To enable our flow algorithms to work under vertex capacities, we also develop a close-to-linear time algorithm for computing length-constrained vertex expander decomposition. Building on Cohen’s idea of path-count flows [8], we further extend our algorithm to solve $(1+\epsilon)$-approximate k-commodity min-cost flow problems with almost-optimal $\hat{O}(m k)$ work and $\hat{O}(1)$ depth, independent of the number of commodities k.

A k-fault-tolerant connectivity preserver of a directed n-vertex graph G is a subgraph H such that, for any edge set F ⊆ E(G) of size |F| ≤ k, the strongly connected components of G−F and H −F are the same. While some graphs require a preserver with Ω(2kn) edges [1], the best-known upper bound is $\tilde O\left( {k{2^k}{n^{2 - /k}}} \right)$ edges [2], leaving a significant gap of Ω(n1−1/k). In contrast, there is no gap in undirected graphs; the optimal bound of Θ(kn) has been well-established since the 90s [3].We nearly close the gap for directed graphs; we prove that there exists a k-fault-tolerant connectivity preserver with O(k4knlogn) edges, and we can construct one with O(8knlog5/2n) edges in poly(2kn) time.Our results also improve the state-of-the-art for a closely related object; a k-connectivity preserver of G is a subgraph H where, for all i ≤ k, the strongly i-connected components of G and H agree. By a known reduction, we obtain a k-connectivity preserver with O(k4knlogn) edges, improving the previous best bound of $\tilde O\left( {k{2^k}{n^{2 - 1/(k - 1)}}} \right)$ [2]. Therefore, for any constant k, our results are optimal to a logn factor for both problems.Lastly, we show that the exponential dependency on k is not inherent for k-connectivity preservers by presenting another construction with $O\left( {n{\text{ }}\sqrt {kn} } \right)$ edges.

We present a faster algorithm for finding a minimum dijoin, a smallest set of edges whose contraction makes a directed graph strongly connected. This problem has been studied since the 1960s [Seshu and Reed 1961] and is dual to finding a maximum sized family of disjoint dicuts [Lucchesi and Younger 1978]. Given a directed graph G with n vertices and m edges whose minimum dijoin has size d, our algorithm outputs both a minimum dijoin and a maximum sized family of disjoint dicuts in O(TC⋅ d) time, where TC = min(mn,n^ω) is the time to compute the transitive closure. This improves upon the state of the art of [Gabow 1993], which requires O(TC ⋅ min(m^{1/2},n^{2/3})) time when d = o(min(m^{1/2},n^{2/3})). Our result extends to finding a minimum weighted dijoin. We achieve this by observing that Frank’s algorithm [Frank 1981] can be sped up when warm-started with a 2-approximation solution, which we observed can be computed in near-linear time.

Given a directed graph G with n vertices and m edges, a parameter k and two disjoint subsets S,T ⊆ V(G), we show that the number of all-subsets important separators, which is the number of A-B important vertex separators of size at most k over all A ⊆ S and B ⊆ T, is at most β(|S|, |T|, k) = 4^k binom(|S|, ≤ k) binom(|T|, ≤ 2k), where binom(x, ≤ c) = ∑_{i = 1}^c binom(x,i), and that they can be enumerated in time 𝒪(β(|S|,|T|,k)k²(m+n)). This is a generalization of the folklore result stating that the number of A-B important separators for two fixed sets A and B is at most 4^k (first implicitly shown by Chen, Liu and Lu Algorithmica '09). From this result, we obtain the following applications: 1) We give a construction for detection sets and sample sets in directed graphs, generalizing the results of Kleinberg (Internet Mathematics' 03) and Feige and Mahdian (STOC' 06) to directed graphs. 2) Via our new sample sets, we give the first FPT algorithm for finding balanced separators in directed graphs parameterized by k, the size of the separator. Our algorithm runs in time 2^{𝒪(k)} ⋅ (m + n). 3) Additionally, we show a 𝒪(√{log k}) approximation algorithm for finding balanced separators in directed graphs in polynomial time. This improves the best known approximation guarantee of 𝒪(√{log n}) and matches the known guarantee in undirected graphs by Feige, Hajiaghayi and Lee (SICOMP' 08). 4) Finally, using our algorithm for listing all-subsets important separators, we give a deterministic construction of vertex cut sparsifiers in directed graphs when we are interested in preserving min-cuts of size upto c between bipartitions of the terminal set. Our algorithm constructs a sparsifier of size 𝒪(binom(t, ≤ 3c)2^{𝒪(c)}) and runs in time 𝒪(binom(t, ≤ 3c) 2^{𝒪(c)}(m + n)), where t is the number of terminals, and the sparsifier additionally preserves the set of important separators of size at most c between bipartitions of the terminals.

We present a dynamic algorithm for maintaining (1+ε)-approximate maximum eigenvector and eigenvalue of a positive semi-definite matrix A undergoing decreasing updates, i.e., updates which may only decrease eigenvalues. Given a vector v updating A ← A-vv^⊤, our algorithm takes Õ(nnz(v)) amortized update time, i.e., polylogarithmic per non-zeros in the update vector. Our technique is based on a novel analysis of the influential power method in the dynamic setting. The two previous sets of techniques have the following drawbacks (1) algebraic techniques can maintain exact solutions but their update time is at least polynomial per non-zeros, and (2) sketching techniques admit polylogarithmic update time but suffer from a crude additive approximation. Our algorithm exploits an oblivious adversary. Interestingly, we show that any algorithm with polylogarithmic update time per non-zeros that works against an adaptive adversary and satisfies an additional natural property would imply a breakthrough for checking psd-ness of matrices in Õ(n²) time, instead of O(n^ω) time.

Unbreakable decomposition, introduced by [CLP+19, CKL+20], has proven to be one of the most powerful tools for parameterized graph cut problems in recent years. Unfortunately, all known constructions require at least Ωk (mn2) time, given an undirected graph with n vertices, m edges, and cut-size parameter k. In this work, we show the first close-to-linear time parameterized algorithm that computes an unbreakable decomposition. More precisely, for any 0 < ∈ ≤ 1, our algorithm runs in time and computes a (O (k/∈ ),k ) unbreakable tree decomposition of the input graph, where each bag has adhesion at most O (k/∈ ).

We give the first deterministic algorithm that makes sub-quadratic queries to find the global min-cut of a simple graph in the cut query model. Given an n-vertex graph G, our algorithm makes Õ (n5/3) queries to compute the global min-cut in G. As a key ingredient, we also show an algorithm for finding s-t max-flows of size Õ (n ) in Õ (n5/3) queries. We also show efficient cut-query implementations of versions of expander decomposition and isolating cuts, which may be of independent interest.

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 consider the problem of assigning short labels to the vertices and edges of a graph G so that given any query 〈s, t, F 〉 with |F | ≤ f, we can determine whether s and t are still connected in G — F, given only the labels of F ∪ {s, t }.

Peer Reviewed

Peer Reviewed

The vertex connectivity of an m -edge n -vertex undirected graph is the smallest number of vertices whose removal disconnects the graph or leaves only a singleton vertex. In 1974, Aho Hopcroft and Ullman asked if vertex connectivity can be computed in linear time. Despite the substantial effort in the past five decades, the best-known running time is \(\tilde{O}(mn)\) by Henzinger-Rao-Gabow (FOCS 1996). Indeed, no algorithm with an o ( mn ) running time is known even if we assume a linear-time max-flow algorithm. In this article, we give an affirmative answer to this long-standing open problem (up to a sub-polynomial factor). We present a randomized reduction from the vertex connectivity problem to the max-flow problem which incurs only a poly-logarithmic overhead in runtime. Using this reduction, we can solve vertex connectivity in almost linear time by using the celebrated almost-linear-time max-flow algorithms by Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and Brand-Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva-Sidford (FOCS 2023). Using our new techniques, we also obtain an algorithm for directed vertex connectivity with a running time of n 2 + o (1) time which improves the best-known bound of \(\tilde{O}(mn)\) by Henzinger-Rao-Gabow (FOCS 1996).

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.

We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph G = (V, E) with$n$vertices undergoing both edge insertions and deletions, and an arbitrary parameter$\epsilon\in[1/\log^{c}n, 1$where$c$> 0 is a small constant, we can deterministically maintain a data structure with$O(n^{\epsilon})$worst-case update time that, given any pair of vertices (u, v), returns a$2^{\text{poly}(1/\epsilon)}$-approximate distance between$u$and$v$in poly(1/E) log log$n$query time. Our algorithm significantly advances the state-of-the-art in two aspects, both for fully dynamic algorithms and even decremental algorithms. First, no existing algorithm with worst-case update time guarantees a o($n$)-approximation while also achieving an n2-Ω(1)update and$n^{o(1)}$query time, while our algorithm offers a constant$O_{\epsilon}(1)$-approximation with$O(n^{\epsilon})$update time and$o_{\epsilon}$(log log n) query time. Second, even if amortized update time is allowed, it is the first deterministic constant-approximation algorithm with$n^{1-\Omega(1)}$update and query time. The best result in this direction is the recent deterministic distance oracle by Chuzhoy and Zhang [STOC 2023] which achieves an approxi- mation of (log log$n)^{2^{O (1 / \epsilon^3)}}$with amortized update time of$O(n^{\epsilon)}$and query time of$2^{\mathrm{p}\circ 1\mathrm{y}(1/\epsilon)}\log n$log log n. We obtain the result by dynamizing tools related to length- constrained expanders [Haeupler-Racke-Ghaffari, STOC 2022; Haeupler-Hershkowitz-Tan, FOCS 2024]. Our technique com- pletely bypasses the 40-year-old Even-Shiloach tree, which has remained the most pervasive tool in the area but is inherently amortized.

We show the first near-linear time randomized algorithms for listing all minimum vertex cuts of polylogarithmic size that separate the graph into at least three connected components (also known as shredders) and for finding the most shattering one, i.e., the one maximizing the number of connected components. Our algorithms break the quadratic time bound by Cheriyan and Thurimella (STOC'96) for both problems that has stood for more than two decades. Our work also removes a bottleneck to near-linear time algorithms for the vertex connectivity augmentation problem (Jordan '95). Note that it is necessary to list only minimum vertex cuts that separate the graph into at least three components because there can be an exponential number of minimum vertex cuts in general. To obtain near-linear time algorithms, we have extended techniques in local flow algorithms developed by Forster et al. (SODA'20) to list shredders on a local scale. We also exploit fast queries to a pairwise vertex connectivity oracle subject to vertex failures (Long and Saranurak FOCS'22, Kosinas ESA'23). This is the first application of connectivity oracles subject to vertex failures to speed up a static graph algorithm.

A cactus representation of a graph, introduced by Dinitz et al. in 1976, is an edge sparsifier of O(n) size that exactly captures all global minimum cuts of the graph. It is a central combinatorial object that has been a key ingredient in almost all algorithms for the connectivity augmentation problems and for maintaining minimum cuts under edge insertions (e.g. [Naor et al. SICOMP’97], [Cen et al. SODA’22], [Henzinger ICALP’95]). This sparsifier was generalized to Steiner cactus for a vertex set T, which can be seen as a vertex sparsifier of O(|T|) size that captures all partitions of T corresponding to a T-Steiner minimum cut, and also hypercactus, an analogous concept in hypergraphs. These generalizations further extend the applications of cactus to the Steiner and hypergraph settings.

Given an undirected weighted graph with n vertices and m edges, we give the first deterministic m1+o(1)-time algorithm for constructing the cactus representation of all global minimum cuts. This improves the current n2+o(1)-time state-of-the-art deterministic algorithm, which can be obtained by combining ideas implicitly from three papers [22, 27, 12]. The known explicitly stated deterministic algorithm has a runtime of Õ(mn) [9, 34]. Using our technique, we can even speed up the fastest randomized algorithm of [23] whose running time is at least Ω(m log4 n) to O(m log3 n).

We study polynomial-time approximation algorithms for edge and vertex Sparsest Cut and Small Set Expansion in terms of k, the number of edges or vertices cut in the optimal solution. Our main results are O(polylog k)-approximation algorithms for various versions in this setting. Our techniques involve an extension of the notion of sample sets (Feige and Mahdian STOC’06), originally developed for small balanced cuts, to sparse cuts in general. We then show how to combine this notion of sample sets with two algorithms, one based on an existing framework of LP rounding and another new algorithm based on the cut-matching game, to get such approximation algorithms. Our cut-matching game algorithm can be viewed as a local version of the cut-matching game by Khandekar, Khot, Orecchia and Vishnoi and certifies an expansion of every vertex set of size s in O(logs) rounds. These techniques may be of independent interest. As corollaries of our results, we also obtain an O(logopt) approximation for min-max graph partitioning, where opt is the min-max value of the optimal cut, and improve the bound on the size of multicut mimicking networks computable in polynomial time.

We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous flow decomposition barrier for multi-commodity flow.

We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2 . Specifically, we obtain a \(1+\tfrac{1}{\sqrt {2}}+\epsilon \approx 1.707+\epsilon\) approximation in bipartite graphs and a \(1.973+\epsilon\) approximation in general graphs. We thus answer in the affirmative the value version of the major open question repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms’ approximation and worst-case update time bounds both hold w.h.p. against adaptive adversaries. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS’21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.

We give the first almost-linear time algorithm for computing the \emph{maximal $k$-edge-connected subgraphs} of an undirected unweighted graph for any constant $k$. More specifically, given an $n$-vertex $m$-edge graph $G=(V,E)$ and a number $k = \log^{o(1)}n$, we can deterministically compute in $O(m+n^{1+o(1)})$ time the unique vertex partition $\{V_{1},\dots,V_{z}\}$ such that, for every $i$, $V_{i}$ induces a $k$-edge-connected subgraph while every superset $V'_{i}\supset V_{i}$ does not. Previous algorithms with linear time work only when $k\le2$ {[}Tarjan SICOMP'72{]}, otherwise they all require $Ω(m+n\sqrt{n})$ time even when $k=3$ {[}Chechik~et~al.~SODA'17; Forster~et~al.~SODA'20{]}. Our algorithm also extends to the decremental graph setting; we can deterministically maintain the maximal $k$-edge-connected subgraphs of a graph undergoing edge deletions in $m^{1+o(1)}$ total update time. Our key idea is a reduction to the dynamic algorithm supporting pairwise $k$-edge-connectivity queries {[}Jin and Sun FOCS'20{]}.

A Gomory-Hu tree (also called a cut tree) succinctly represents $(s, t)$ min-cuts (and therefore, $(s, t)$ max-flow values) of all pairs of vertices $s, t$ in an undirected graph. In this paper, we give an $m^{1+o(1)}$-time algorithm for constructing a Gomory-Hu tree for a graph with m edges. This shows that the all-pairs max-flows problem has the same running time as the single-pair max-flow problem, up to a subpolynomial factor. Prior to our work, the best known Gomory-Hu tree algorithm was obtained in recent work by Abboud et al. (FOCS 2022) and requires $\tilde{O}\left(n^{2}\right)$ time for a graph with n vertices. Our result marks a natural culmination of over 60 years of research into the all-pairs maxflows problem that started with Gomory and Hu’s pathbreaking result introducing the Gomory-Hu tree in 1961.

We study the problem of chasing positive bodies in $\ell_{1}$: given a sequence of bodies $K_{t}=\left\{x^{t} \in \mathbb{R}_{+}^{n} \mid C^{t} x^{t} \geq 1, P^{t} x^{t} \leq 1\right\}$ revealed online, where $C^{t}$ and $P^{t}$ are nonnegative matrices, the goal is to (approximately) maintain a point $x_{t} \in K_{t}$ such that $\sum_{t}\left\|x_{t}-x_{t-1}\right\|_{1}$ is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching.We give an $O(\log d)$-competitive algorithm for this problem, where d is the maximum row sparsity of any matrix $C^{t}$. This bypasses and improves exponentially over the lower bound of $\sqrt{n}$ known for general convex bodies. Our algorithm is based on iterated information projections, and, in contrast to general convex body chasing algorithms, is entirely memoryless.We also show how to round our solution dynamically to obtain the first fully dynamic algorithms with competitive recourse for all the stated problems above; i.e. their recourse is less than the recourse of every other algorithm on every update sequence, up to polylogarithmic factors. This is a significantly stronger notion than the notion of absolute recourse in the dynamic algorithms literature.

We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate size of maximum matching of the graph with n vertices and m edges using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial improvement over the long-standing $O(n)$ update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS’13], [Bernstein and Stein SODA’16], [Behnezhad and Khanna SODA’22]). Our key technical component is the first sublinear algorithm for $(1, \epsilon n)$-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least 1.499 or assumed that the graph has a very small maximum degree.

We introduce the notion of fair cuts as an approach to leverage approximate (s, t)-mincut (equivalently (s, t)-maxflow) algorithms in undirected graphs to obtain near-linear time approximation algorithms for several cut problems. Informally, for any α ≥ 1, an α-fair (s, t)-cut is an (s, t)-cut such that there exists an (s, t)-flow that uses 1/α fraction of the capacity of every edge in the cut. (So, any α-fair cut is also an α-approximate mincut, but not vice-versa.) We give an algorithm for (1 + ε)-fair (s, t)-cut in Õ(m)-time, thereby matching the best runtime for (1 + ε)-approximate (s, t)-mincut [Peng, SODA '16]. We then demonstrate the power of this approach by showing that this result almost immediately leads to several applications: • the first nearly-linear time (1 + ε)-approximation algorithm that computes all-pairs maxflow values (by constructing an approximate Gomory-Hu tree). Prior to our work, such a result was not known even for the special case of Steiner mincut [Dinitz and Vainstein, STOC '94; Cole and Hariharan, STOC '03]; • the first almost-linear-work subpolynomial-depth parallel algorithms for computing (1+ε)-approximations for all-pairs maxflow values (again via an approximate Gomory-Hu tree) in unweighted graphs; • the first near-linear time expander decomposition algorithm that works even when the expansion parameter is polynomially small; this subsumes previous incomparable algorithms [Nanongkai and Saranurak, FOCS '17; Wulff-Nilsen, FOCS '17; Saranurak and Wang, SODA '19]. * The full version of the paper can be accessed at https://arxiv.org/abs/2203.00751

In the dynamic linear program (LP) problem, we are given an LP undergoing updates and we need to maintain an approximately optimal solution. Recently, significant attention (e.g. [Gupta et al. STOC'17; Arar et al. ICALP'18, Wajc STOC'20]) has been devoted to the study of special cases of dynamic packing and covering LPs, such as the dynamic fractional matching and set cover problems. But until now, there is no non-trivial dynamic algorithm for general packing and covering LPs.

We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. Specifically, we obtain a approximation in bipartite graphs and a 1.973 + ε approximation in general graphs. We thus answer in the affirmative the value version of the major open question repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms' approximation and worst-case update time bounds both hold w.h.p. against adaptive adversaries. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.

Given a simple n-vertex, m-edge graph G undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of G in Õ(n) worst-case update time and Õ(m1-1/16) amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results answer in the affirmative an open question posed by Thorup [Combinatorica'07].

The maximal k-edge-connected subgraphs problem is a classical graph clustering problem studied since the 70's. Surprisingly, no non-trivial technique for this problem in weighted graphs is known: a very straightforward recursive-min-cut algorithm with Ω(mn) time has remained the fastest algorithm until now. All previous progress gives a speed-up only when the graph is unweighted, and k is small enough (e.g. Henzinger et al. (ICALP'15), Chechik et al. (SODA'17), and Forster et al. (SODA'20)). We give the first algorithm that breaks through the long-standing Õ(mn)-time barrier in weighted undirected graphs. More specifically, we show a maximal k-edge-connected subgraphs algorithm that takes only Õ(m · min{m3/4,n4/5}) time. As an immediate application, we can (1 + ε)-approximate the strength of all edges in undirected graphs in the same running time. Our key technique is the first local cut algorithm with exact cut-value guarantees whose running time depends only on the output size. All previous local cut algorithms either have running time depending on the cut value of the output, which can be arbitrarily slow in weighted graphs or have approximate cut guarantees.

We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad ‍[FOCS’22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. ‍[SODA’23] improved the approximation factor to (2−1/2O(1/γ)) using n1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n2−Ω(1) time.

Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as h-length flows which are defined as flows whose flow paths have length at most h. Many well-studied algorithmic primitives—such as maximal and maximum length-constrained disjoint paths—are special cases of h-length flows. Likewise the optimal h-length flow is a fundamental quantity in network optimization, characterizing, up to poly-log factors, how quickly a network can accomplish numerous distributed primitives.

We study the fine-grained complexity of graph connectivity problems in unweighted undirected graphs. Recent development shows that all variants of edge connectivity problems, including single-source-single-sink, global, Steiner, single-source, and all-pairs connectivity, are solvable in m1+o(1) time, collapsing the complexity of these problems into the almost-linear-time regime. While, historically, vertex connectivity has been much harder, the recent results showed that both single-source-single-sink and global vertex connectivity can be solved in m1+o(1) time, raising the hope of putting all variants of vertex connectivity problems into the almost-linear-time regime too.

Designing dynamic algorithms against an adaptive adversary whose performance match the ones assuming an oblivious adversary is a major research program in the field of dynamic graph algorithms. One of the prominent examples whose oblivious-vs-adaptive gap remains maximally large is the \emph{fully dynamic spanner} problem; there exist algorithms assuming an oblivious adversary with near-optimal size-stretch trade-off using only $\operatorname{polylog}(n)$ update time [Baswana, Khurana, and Sarkar TALG'12; Forster and Goranci STOC'19; Bernstein, Forster, and Henzinger SODA'20], while against an adaptive adversary, even when we allow infinite time and only count recourse (i.e. the number of edge changes per update in the maintained spanner), all previous algorithms with stretch at most $\log^{5}(n)$ require at least $Ω(n)$ amortized recourse [Ausiello, Franciosa, and Italiano ESA'05]. In this paper, we completely close this gap with respect to recourse by showing algorithms against an adaptive adversary with near-optimal size-stretch trade-off and recourse. More precisely, for any $k\ge1$, our algorithm maintains a $(2k-1)$-spanner of size $O(n^{1+1/k}\log n)$ with $O(\log n)$ amortized recourse, which is optimal in all parameters up to a $O(\log n)$ factor. As a step toward algorithms with small update time (not just recourse), we show another algorithm that maintains a $3$-spanner of size $\tilde O(n^{1.5})$ with $\operatorname{polylog}(n)$ amortized recourse \emph{and} simultaneously $\tilde O(\sqrt{n})$ worst-case update time.

Recently, Chalermsook et al. [SODA'21(arXiv:2007.07862)] introduces a notion of vertex sparsifiers for $c$-edge connectivity, which has found applications in parameterized algorithms for network design and also led to exciting dynamic algorithms for $c$-edge st-connectivity [Jin and Sun FOCS'21(arXiv:2004.07650)]. We study a natural extension called vertex sparsifiers for $c$-hyperedge connectivity and construct a sparsifier whose size matches the state-of-the-art for normal graphs. More specifically, we show that, given a hypergraph $G=(V,E)$ with $n$ vertices and $m$ hyperedges with $k$ terminal vertices and a parameter $c$, there exists a hypergraph $H$ containing only $O(kc^{3})$ hyperedges that preserves all minimum cuts (up to value $c$) between all subset of terminals. This matches the best bound of $O(kc^{3})$ edges for normal graphs by [Liu'20(arXiv:2011.15101)]. Moreover, $H$ can be constructed in almost-linear $O(p^{1+o(1)} + n(rc\log n)^{O(rc)}\log m)$ time where $r=\max_{e\in E}|e|$ is the rank of $G$ and $p=\sum_{e\in E}|e|$ is the total size of $G$, or in $\text{poly}(m, n)$ time if we slightly relax the size to $O(kc^{3}\log^{1.5}(kc))$ hyperedges.

In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all $\begin{pmatrix}n\\2\end{pmatrix}$ pairs of vertices in an undirected graph can be solved using only $n-1$ calls to any (single-pair) max-flow algorithm. Even assuming a linear-time max-flow algorithm, this yields a running time of $O(mn)$, which is $O(n^{3})$ when $m=\Theta(n^{2})$. While subsequent work has improved this bound for various special graph classes, no subcubic-time algorithm has been obtained in the last 60 years for general graphs. We break this longstanding barrier by giving an $\tilde{O}(n^{2})$-time algorithm on general, integer-weighted graphs. Combined with a popular complexity assumption, we establish a counter-intuitive separation: all-pairs max-flows are strictly easier to compute than all-pairs shortest-paths.Our algorithm produces a cut-equivalent tree, known as the Gomory-Hu tree, from which the max-flow value for any pair can be retrieved in near-constant time. For unweighted graphs, we refine our techniques further to produce a Gomory-Hu tree in the time of a poly-logarithmic number of calls to any maxflow algorithm. This shows an equivalence between the all-pairs and single-pair max-flow problems, and is optimal up to polylogarithmic factors. Using the recently announced $m^{1+o(1)}$-time max-flow algorithm (Chen et al., March 2022), our Gomory-Hu tree algorithm for unweighted graphs also runs in $m^{1+o(1)}$-time.

We revisit the vertex-failure connectivity oracle problem. This is one of the most basic graph data structure problems under vertex updates, yet its complexity is still not well-understood. We essentially settle the complexity of this problem by showing a new data structure whose space, preprocessing time, update time, and query time are simultaneously optimal up to sub-polynomial factors assuming popular conjectures. Moreover, the data structure is deterministic.More precisely, for any integer $d_{\star}$, the data structure preprocesses a graph G with n vertices and m edges in $\hat{O}\left(m d_{\star}\right)$ time and uses $\tilde{O}\left(\min \left\{m, n d_{\star}\right\}\right)$ space. Then, given the vertex set D to be deleted where $|D|=d \leq d_{\star}$, it takes $\hat{O}\left(d^{2}\right)$ updates time. Finally, given any vertex pair $(u, v)$, it checks if u and v are connected in $G \backslash D$ in $O(d)$ time. This improves the previously best deterministic algorithm by Duan and Pettie [SICOMP 2020] in both space and update time by a factor of d. It also significantly speeds up the $\Omega\left(\min \left\{m n, n^{\omega}\right\}\right)$ preprocessing time of all known (even randomized) algorithms with update time at most $\tilde{O}\left(d^{5}\right)$.

In the vertex connectivity problem, given an undirected n-vertex m-edge graph G, we need to compute the minimum number of vertices that can disconnect G after removing them. This problem is one of the most well-studied graph problems. From 2019, a new line of work [Nanongkai et al. STOC’19;SODA’20;STOC’21] has used randomized techniques to break the quadratic-time barrier and, very recently, culminated in an almost-linear time algorithm via the recently announced maxflow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm [Gabow FOCS’00] takes $O(m(n+min\{c^{5/2}, cn^{3/4}\}))$ time where c is the vertex connectivity. It remains open whether there exists a subquadratic-time deterministic algorithm for any constant c > 3. In this paper, we give the first deterministic almost-linear time vertex connectivity algorithm for all constants c. Our running time is $m^{1+o(1)}2^{O(c^{2})}$ time, which is almost-linear for all $c=o(\sqrt{\log n})$. This is the first deterministic algorithm that breaks the $O(n^{2})$-time bound on sparse graphs where $m=O(n)$, which is known for more than 50 years ago [Kleitman’69]. Towards our result, we give a new reduction framework to vertex expanders which in turn exploits our new almost-linear time construction of mimicking network for vertex connectivity. The previous construction by Kratsch and Wahlström [FOCS’12] requires large polynomial time and is randomized.

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 k-edge-connected spanning subgraph (kECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to k link failures: Given an n-node m-edge graph with a cost function on the edges, our goal is to compute a minimum-cost k-edge-connected spanning subgraph. This NP-hard problem generalizes the minimum spanning tree problem and is the "uniform case" of a much broader class of survival network design problems (SNDP). A factor of two has remained the best approximation ratio for polynomial-time algorithms for the whole class of SNDP, even for a special case of 2ECSS. The fastest 2-approximation algorithm is however rather slow, taking O(mn k) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n²) can be obtained, but with a higher approximation guarantee of (2k-1) [Gabow, Goemans, Williamson, IPCO'93]. Our main contribution is an algorithm that (1+ε)-approximates the optimal fractional solution in Õ(m/ε²) time (independent of k), which can be turned into a (2+ε) approximation algorithm that runs in time Õ(m/(ε²) + {k²n^{1.5}}/ε²) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two.

Given an input that undergoes a sequence of updates, a dynamic algorithm maintains a valid solution to some predefined problem at any point in time; the goal is to design an algorithm in which computing a solution to the updated input is done more efficiently than computing the solution from scratch. A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain faster dynamic algorithms against an adaptive adversary and separation results between what is achievable in the oblivious vs. adaptive settings. To get these results we exploit techniques from differential privacy, cryptography, and adaptive data analysis. Our results are as follows.

A k-vertex connectivity oracle for undirected G is a data structure that, given u,v∈ V(G), reports min{k,κ(u,v)}, where κ(u,v) is the pairwise vertex connectivity between u,v. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov [Inf. Process. Lett. 2012] shows that a data structure of total size O(knlogn), which can even be encoded as a O(klog3 n)-bit labeling scheme, can answer vertex-connectivity queries in O(klogn) time. The construction time is polynomial, but unspecified.

We give an$n^{2+o(1)}$-time algorithm for finding$s-t$min-cuts for all pairs of vertices$s$and$t$in a simple, undirected graph on$n$vertices. We do so by constructing a Gomory-Hu tree (or cut equivalent tree) in the same running time, thereby improving on the recent bound of$\tilde{O}(n^{2.5})$by Abboud et al. (STOC 2021). Our running time is nearly optimal as a function of$n$.

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 give an algorithm to find a minimum cut in an edge-weighted directed graph with$n$vertices and$m$edges in$\tilde{O}(n\cdot\max\{m^{2/3},\ n\})$time. This improves on the 30 year old bound of$\tilde{O}(nm)$obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain$\tilde{O}(n^{2}/\epsilon^{2})$-time$(1+{\epsilon})$-approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed$\epsilon$. Before our work, no (1 +$\epsilon)$-approximation algorithm better than the exact runtime of$\tilde{O}(nm)$is known for either problem. Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to$\tilde{O}(\min\{{n}/m^{1/3}, \sqrt{n}\}){-}$calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.

In the decremental single-source shortest paths (SSSP) problem, the input is an undirected graph G = (V, E) with n vertices and m edges undergoing edge deletions, together with a fixed source vertex s ∊ V. The goal is to maintain a data structure that supports shortest-path queries: given a vertex v ∊ V, quickly return an (approximate) shortest path from s to v. The decremental all-pairs shortest paths (APSP) problem is defined similarly, but now the shortest-path queries are allowed between any pair of vertices of V. Both problems have been studied extensively since the 80's, and algorithms with near-optimal total update time and query time have been discovered for them. Unfortunately, all these algorithms are randomized and, more importantly, they need to assume an oblivious adversary – a drawback that prevents them from being used as subroutines in several known algorithms for classical static problems. In this paper, we provide new deterministic algorithms for both problems, which, by definition, can handle an adaptive adversary. Our first result is a deterministic algorithm for the decremental SSSP problem on weighted graphs with O(n2+o(1)) total update time, that supports (1 + ∊)-approximate shortest-path queries, with query time O(|P| · no(1)), where P is the returned path. This is the first (1 + ∊)-approximation adaptive-update algorithm supporting shortest-path queries in time below O(n), that breaks the O(mn) total update time bound of the classical algorithm of Even and Shiloah from 1981. Previously, Bernstein and Chechik [STOC'16, ICALP'17] provided a Õ(n2)-time deterministic algorithm that supports approximate distance queries, but unfortunately the algorithm cannot return the approximate shortest paths. Chuzhoy and Khanna [STOC'19] showed an O(n2+o(1))-time randomized algorithm for SSSP that supports approximate shortest-path queries in the adaptive adversary regime, but their algorithm only works in the restricted setting where only vertex deletions, and not edge deletions are allowed, and it requires Ω(n) time to respond to shortest-path queries. Our second result is a deterministic algorithm for the decremental APSP problem on unweighted graphs that achieves total update time O(n2.5+δ), for any constant δ > 0, supports approximate distance queries in O(log log n) time, and supports approximate shortest-path queries in time O(|E(P)| · no(1)), where P is the returned path; the algorithm achieves an O(1)-multiplicative and no(1)-additive approximation on the path length. All previous algorithms for APSP either assume an oblivious adversary or have an Ω(n3) total update time when m = Ω(n2), even if an o(n)-multiplicative approximation is allowed. To obtain both our results, we improve and generalize the layered core decomposition data structure introduced by Chuzhoy and Khanna to be nearly optimal in terms of various parameters, and introduce a new generic approach of rooting Even-Shiloach trees at expander sub-graphs of the given graph. We believe both these technical tools to be interesting in their own right and anticipate them to be useful for designing future dynamic algorithms that work against an adaptive adversary.

We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with n vertices undergoing edge insertions and deletions using no(1) update time. An expander hierarchy is a tree representation of graphs that faithfully captures the cut-flow structure and consequently our dynamic algorithm almost immediately implies several results including: The first fully dynamic algorithm with no(1) worst-case update time that allows querying no(1)-approximate conductance, s-t maximum flows, and s-t minimum cuts for any given (s, t) in O(log1/6 n) time. Our results are deterministic and extend to multi-commodity cuts and flows. All previous fully dynamic (or even decremental) algorithms for any of these problems take Ω(n) update or query time. The key idea behind these results is a fully dynamic algorithm for maintaining a tree flow sparsifier, a notion introduced by Räcke [FOCS'02] for constructing competitive oblivious routing schemes. A deterministic fully dynamic connectivity algorithm with no(1) worst-case update time. This significantly simplifies the recent algorithm by Chuzhoy et al. that uses the framework of Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17]. A deterministic fully dynamic treewidth decomposition algorithm on constant-degree graphs with no(1) worst-case update time that maintains a treewidth decomposition of width tw(G) · no(1) where tw(G) denotes the treewidth of the current graph. This is the first non-trivial dynamic algorithm for this problem. Our technique is based on a new stronger notion of the expander decomposition, called the boundary-linked expander decomposition. This decomposition is more robust against updates and better captures clustering structure of graphs compared to the standard expander decomposition. Given that the expander decomposition has proved extremely useful in many fields, including approximation, sketching, distributed, and dynamic algorithms, we expect that our new notion will find more future applications.

In this paper we provide new randomized algorithms with improved runtimes for solving linear programs with two-sided constraints. In the special case of the minimum cost flow problem on n-vertex m-edge graphs with integer polynomially-bounded costs and capacities we obtain a randomized method which solves the problem in Õ(m + n1.5) time. This improves upon the previous best runtime of Õ(m √n) [Lee-Sidford’14] and, in the special case of unit-capacity maximum flow, improves upon the previous best runtimes of m4/3 + o(1) [Liu-Sidford’20, Kathuria’20] and Õ(m √n) [Lee-Sidford’14] for sufficiently dense graphs.

The vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in (mα) time for any α ≥ 1, if there is a mα-time maxflow algorithm. Using the current best maxflow algorithm that runs in m4/3+o(1) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m4/3+o(1)-time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an Õ(mn)-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o(mn) running time was known before our work, even if we assume an (m)-time maxflow algorithm.

We present improved distributed algorithms for variants of the triangle finding problem in the model. We show that triangle detection, counting, and enumeration can be solved in rounds using expander decompositions . This matches the triangle enumeration lower bound of by Izumi and Le Gall [PODC’17] and Pandurangan, Robinson, and Scquizzato [SPAA’18], which holds even in the model. The previous upper bounds for triangle detection and enumeration in were and , respectively, due to Izumi and Le Gall [PODC’17]. An -expander decomposition of a graph is a clustering of the vertices such that (i) each cluster induces a subgraph with conductance at least and (ii) the number of inter-cluster edges is at most . We show that an -expander decomposition with can be constructed in rounds for any and positive integer . For example, a -expander decomposition only requires rounds to compute, which is optimal up to subpolynomial factors, and a -expander decomposition can be computed in rounds, for any arbitrarily small constant . Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate algorithms with small overhead by applying the expander routing algorithm due to Ghaffari, Kuhn, and Su [PODC’17] Finally, we deal with inter-cluster edges using recursive calls.

The dynamic optimality conjecture, postulating the existence of an $O(1)$-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. Despite extensive work and some notable progress, including, for example, the Tango Trees (Demaine et al., FOCS 2004), that give the best currently known $O(\log \log n)$-competitive algorithm, the conjecture remains widely open. One of the main hurdles towards settling the conjecture is that we currently do not have approximation algorithms achieving better than an $O(\log \log n)$-approximation, even in the offline setting. All known non-trivial algorithms for BST's so far rely on comparing the algorithm's cost with the so-called Wilber's first bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right. Our contribution is two-fold. First, we show that the gap between the WB-1 bound and the optimal solution value can be as large as $Ω(\log \log n/ \log \log \log n)$; in fact, the gap holds even for several stronger variants of the bound. Second, we provide a simple algorithm, that, given an integer $D>0$, obtains an $O(D)$-approximation in time $\exp\left(O\left (n^{1/2^{Ω(D)}}\log n\right )\right )$. In particular, this gives a constant-factor approximation sub-exponential time algorithm. Moreover, we obtain a simpler and cleaner efficient $O(\log \log n)$-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call {\em Guillotine Bound}, that is stronger than WB, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis.

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.

We present an ~O(m+n1.5)-time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, and optimal transport) on m-edge, n-node graphs. For maximum cardinality bipartite matching on moderately dense graphs, i.e. m=Ω(n1.5), our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic O(m√n)-time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and ~O(nω)-time algorithms [Ibarra-Moran 1981] (where currently ω ≈ 2.373). On sparser graphs, i.e. when m=n9/8+δfor any constant , our result improves upon the recent advances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an ~O(m4/3+o(1)) runtime. We obtain these results by combining and advancing recent lines of research in interior point methods (IPMs) and dynamic graph algorithms. First, we simplify and improve the IPM of [v.d.Brand-Lee-Sidford-Song 2020], providing a general primal-dual IPM framework and new sampling-based techniques for handling infeasibility induced by approximate linear system solvers. Second, we provide a simple sublinear-time algorithm for detecting and sampling high-energy edges in electric flows on expanders and show that when combined with recent advances in dynamic expander decompositions, this yields efficient data structures for maintaining the iterates of both [v.d.Brand et al.] and our new IPMs. Combining this general machinery yields a simpler ~O(n√m) time algorithm for matching based on the logarithmic barrier function, and our state-of-the-art ~O(m+n1.5) time algorithm for matching based on the [Lee-Sidford 2014] barrier (as regularized in [v.d.Brand et al.]).

There is a recent exciting line of work in distributed graph algorithms in the CONGEST model that exploit expanders. All these algorithms so far are based on two tools: expander decomposition and expander routing. An ( ε, φ)-expander decomposition removes ε-fraction of the edges so that the remaining connected components have conductance at least φ, i.e., they are φ-expanders, and expander routing allows each vertex v in a φ-expander to very quickly exchange deg(v) messages with any other vertices, not just its local neighbors. In this paper, we give the first efficient deterministic distributed algorithms for both tools. We show that an ( ε, φ) -expander decomposition can be deterministically computed in poly (ε-1)no(1)rounds for φ = poly (ε)n-o(1), and that expander routing can be performed deterministically in poly (φ-1)no(1)rounds. Both results match previous bounds of randomized algorithms by [Chang and Saranurak, PODC 2019] and [Ghaffari, Kuhn, and Su, PODC 2017] up to subpolynomial factors. Consequently, we derandomize existing distributed algorithms that exploit expanders. We show that a minimum spanning tree on n-o(1)-expanders can be constructed deterministically in no(1)rounds, and triangle detection and enumeration on general graphs can be solved deterministically in O(n0.58) and n2/3+o(1)rounds, respectively. Using similar techniques, we also give the first polylogarithmic-round randomized algorithm for constructing an ( ε, φ) -expander decomposition in poly (ε-1, logn) rounds for φ = 1/poly(ε-1, logn). This algorithm is faster than the previous algorithm by [Chang and Saranurak, PODC 2019] in all regimes of parameters. The previous algorithm needs nΩ(1)rounds for any φ ≥ 1/polylogn.

We present a general framework of designing efficient dynamic approximate algorithms for optimization problems on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1)A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in ~O(n2/3)11The ~O(·) notation is used in this paper to hide poly-logarithmic factors. amortized time against an oblivious adversary, and ~O(m3/4) time against an adaptive adversary. (2)An incremental data structure that maintains O(1) - approximate shortest path in no(1)time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in ~O(n2/3+o(1)) amortized time per operation. (3)A fully-dynamic algorithm that approximates all-pair effective resistance up to an ( 1+ε) factor in ~O(n2/3+o(1)ε-O(1)) amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as j-trees) and approximately captures the cut-flow and metric structure of the graph. The O(1)-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. See https://arxiv.org/pdf/2005.02368.pdf for the full version of this paper.

We consider the classical Minimum Balanced Cut problem: given a graph G, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first deterministic, almost-linear time approximation algorithm for this problem. Specifically, our algorithm, given an n-vertex m-edge graph G and any parameter 1 ≤ r ≤ O(logn), computes a (logm)r2-approximation for Minimum Balanced Cut in G, in time O(m1+O(1/r)+o(1)·(logm)O(r2)). In particular, we obtain a (logm)1/ε-approximation in time m1+O(√{ε})for any constant , and a (logm)f(m)-approximation in time m1+o(1), for any slowly growing function f(m). We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of G that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an n-vertex graph is no(1), thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in n factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.

To date, the only way to argue polynomial lower bounds for dynamic algorithms is via fine-grained complexity arguments. These arguments rely on strong assumptions about specific problems such as the Strong Exponential Time Hypothesis (SETH) and the Online Matrix-Vector Multiplication Conjecture (OMv). While they have led to many exciting discoveries, dynamic algorithms still miss out some benefits and lessons from the traditional “coarse-grained” approach that relates together classes of problems such as P and NP. In this paper we initiate the study of coarse-grained complexity theory for dynamic algorithms. Below are among questions that this theory can answer. What if dynamic Orthogonal Vector (OV) is easy in the cell-probe model? A research program for proving polynomial unconditional lower bounds for dynamic OV in the cell-probe model is motivated by the fact that many conditional lower bounds can be shown via reductions from the dynamic OV problem (e.g. [Abboud, V.-Williams, FOCS 2014]). Since the cell-probe model is more powerful than word RAM and has historically allowed smaller upper bounds (e.g. [Larsen, Williams, SODA 2017; Chakraborty, Kamma, Larsen, STOC 2018]), it might turn out that dynamic OV is easy in the cell-probe model, making this research direction infeasible. Our theory implies that if this is the case, there will be very interesting algorithmic consequences: If dynamic OV can be maintained in polylogarithmic worst-case update time in the cell-probe model, then so are several important dynamic problems such as k-edge connectivity, (1 + ϵ)-approximate mincut, (1 + ϵ)-approximate matching, planar nearest neighbors, Chan's subset union and 3-vs-4 diameter. The same conclusion can be made when we replace dynamic OV by, e.g., subgraph connectivity, single source reachability, Chan's subset union, and 3-vs-4 diameter. Lower bounds for k-edge connectivity via dynamic OV? The ubiquity of reductions from dynamic OV raises a question whether we can prove conditional lower bounds for, e.g., k-edge connectivity, approximate mincut, and approximate matching, via the same approach. Our theory provides a method to refute such possibility (the so-called non-reducibility). In particular, we show that there are no “efficient” reductions (in both cell-probe and word RAM models) from dynamic OV to k-edge connectivity under an assumption about the classes of dynamic algorithms whose analogue in the static setting is widely believed. We are not aware of any existing assumptions that can play the same role. (The NSETH of Carmosino et al. [ITCS 2016] is the closest one, but is not enough.) To show similar results for other problems, one only need to develop efficient randomized verification protocols for such problems.

Consider the following “local” cut-detection problem in a directed graph: We are given a seed vertex x and need to remove at most k edges so that at most v edges can be reached from x (a “local” cut) or output ⊥ to indicate that no such cut exists. If we are given query access to the input graph, then this problem can in principle be solved without reading the whole graph and with query complexity depending on k and ν. In this paper we consider a slack variant of this problem where, when such a cut exists, we can output a cut with up to O(kν) edges reachable from x. We present a simple randomized algorithm spending O(k2ν) time and O(kν) queries for the above variant, improving in particular a previous time bound of O(kO(k)ν) by Chechik et al. [SODA’17]. We also extend our algorithm to handle an approximate variant. We demonstrate that these local algorithms are versatile primitives for designing substantially improved algorithms for classic graph problems by providing the following three applications. (Throughout, Õ(T) hides polylog(T).) A randomized algorithm for the classic k-vertex connectivity problem that takes near-linear time when k = O(polylog(n)), namely Õ(m + nk3) time in undirected graphs. Prior to our work, the state of the art for this range of k were linear-time algorithms for k ≤ 3 [Tarjan FOCS’71; Hopcroft, Tarjan SICOMP’73] and a recent algorithm with Õ(m + n4/3k7/3) time [Nanongkai et al., STOC’19]. The story is the same for directed graphs where our Õ(mk2)-time algorithm is near-linear when k = O(polylog(n)). Our techniques also yield an improved approximation scheme. Property testing algorithms for k-edge and -vertex connectivity with query complexities that are near-linear in k, exponentially improving the state-of-the-art. This resolves two open problems, one by Goldreich and Ron [STOC’97] and one by Orenstein and Ron [Theor. Comput. Sci.’11]. A faster algorithm for computing the maximal k-edge connected subgraphs, improving prior work of Chechik et al. [SODA’17].

We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of data structures [B. Allen and I. Munro, J. ACM, 25 (1978), pp. 526--535; D. D. Sleator and R. E. Tarjan, J. ACM, 32 (1985), pp. 652--686; M. L. Fredman et al., Algorithmica, 1 (1986), pp. 111--129; R. Wilber, SIAM J. Comput., 18 (1989), pp. 56--67; M. L. Fredman, in WAE 1999, Springer, Berlin, 1999, pp. 244--258; J. Iacono and Ö. Özkan, in ICALP 2014, Springer, Berlin, 2014, pp. 637--649]. Roughly speaking, we map an arbitrary heap algorithm within a natural model, to a corresponding BST algorithm with the same cost on a dual sequence of operations (i.e., the same sequence with the roles of time and key-space switched). This is the first general transformation between the two families of data structures. There is a rich theory of dynamic optimality for BSTs (i.e., the theory of competitiveness between BST algorithms). The lack of an analogous theory for heaps has been noted in the literature (e.g., [S. Pettie, in FOCS 2005, IEEE, Washington, DC, 2005, pp. 174--183; S. Pettie, in SODA 2008, ACM, New York, SIAM, Philadelphia, 2008, pp. 1115--1124]). Through our connection, we transfer all instance-specific lower bounds known for BSTs to a general model of heaps, initiating a theory of dynamic optimality for heaps. On the algorithmic side, we obtain a new, simple, and efficient heap algorithm, which we call the smooth heap. We show the smooth heap to be the heap-counterpart of Greedy, the BST algorithm with the strongest proven and conjectured properties from the literature, widely believed to be instance-optimal [J. M. Lucas, Canonical Forms for Competitive Binary Search Tree Algorithms, Tech. rep. DCS-TR-250, Rutgers University, New Brunswick, NJ, 1988; J. Munro, in Algorithms---ESA 2000, Lecture Notes in Comput. Sci. 1879, Springer, Berlin, Heidelberg, 2000, pp. 338--345; E. D. Demaine et al., in SODA 2009, AMC, New York, SIAM, Philadelphia, 2009, pp. 496--505]. Assuming the optimality of Greedy, the smooth heap is also optimal within our model of heap algorithms. As corollaries of results known for Greedy, we obtain instance-specific upper bounds for the smooth heap, with applications in adaptive sorting. Intriguingly, the smooth heap, although derived from a non-practical BST algorithm, is simple and easy to implement (e.g., it stores no auxiliary data besides the keys and tree pointers). It can be seen as a variation on the popular pairing heap data structure, extending it with a “power-of-two-choices” type of heuristic.

The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynamic problems whose complexity is not yet well-understood, such as maintaining the largest eigenvalue, rank and determinant of a matrix and maintaining reachability, distances, maximum matching size, and k-paths/cycles in a graph. Understanding the complexity of dynamic matrix inverse is a key to understand these problems. In this paper, we present (i) improved algorithms for dynamic matrix inverse and their extensions to some incremental/look-ahead variants, and (ii) variants of the Online Matrix-Vector conjecture [Henzinger~et~al. STOC'15] that, if true, imply that these algorithms are tight. Our algorithms automatically lead to faster dynamic algorithms for the aforementioned problems, some of which are also tight under our conjectures, e.g. reachability and maximum matching size (closing the gaps for these two problems was in fact asked by Abboud and V. Williams [FOCS'14]). Prior best bounds for most of these problems date back to more than a decade ago [Sankowski FOCS'04, COCOON'05, SODA'07; Kavitha FSTTCS'08; Mucha and Sankowski Algorithmica'10; Bosek et al. FOCS'14]. Our improvements stem mostly from the ability to use fast matrix multiplication “one more time'', to maintain a certain transformation matrix which could be maintained only combinatorially previously (i.e. without fast matrix multiplication). Oddly, unlike other dynamic problems where this approach, once successful, could be repeated several times (“bootstrapping''), our conjectures imply that this is not the case for dynamic matrix inverse and some related problems. However, when a small additional “look-ahead'' information is provided we can perform such repetition to drive the bounds down further.

In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph G with n nodes and integer weights from [-W,W]. Second, given a single batch of f edge insertions and deletions, we update the data structure. Third, given a query pair of nodes (u,v), return the distance from u to v. In the easier problem called sensitive reachability oracle problem, we only ask if there exists a directed path from u to v. Our first result is a sensitive distance oracle with Õ(Wnω+(3-ω)μ) preprocessing time, Õ(Wn2-μf2+ Wnfω) update time, and Õ(Wn2-μf + Wnf2) query time where the parameter μ ϵ [0,1] can be chosen. The data-structure requires O(Wn2+μlog n) bits of memory. This is the first algorithm that can handle f ≥ log n updates. Previous results (e.g. [Demetrescu et al. SICOMP'08; Bernstein and Karger SODA'08 and FOCS'09; Duan and Pettie SODA'09; Grandoni and Williams FOCS'12]) can handle at most 2 updates. When 3 ≤ f ≤ log n, the only non-trivial algorithm was by [Weimann and Yuster FOCS'10]. When W = Õ(1), our algorithm simultaneously improves their preprocessing time, update time, and query time. In particular, when f = ω(1), their update and query time is Ω(n2-o(1)), while our update and query time are truly subquadratic in n, i.e., ours is faster by a polynomial factor of n. To highlight the technique, ours is the first graph algorithm that exploits the kernel basis decomposition of polynomial matrices by [Jeannerod and Villard J.Comp'05; Zhou, Labahn and Storjohann J.Comp'15] developed in the symbolic computation community. As an easy observation from our technique, we obtain the first sensitive reachability oracle can handle f≥log n updates. Our algorithm has O(nω) preprocessing time, O(fω) update time, and O(f2) query time. This data-structure requires O(n2log n) bits of memory. Efficient sensitive reachability oracles were asked in [Chechik, Cohen, Fiat, and Kaplan SODA'17]. Our algorithm can handle any constant number of updates in constant time. Previous algorithms with constant update and query time can handle only at most f ≤ 2 updates. Otherwise, there are non-trivial results for f ≤ log n, though, with query time Ω(n) by adapting [Baswana, Choudhary and Roditty STOC'16].

An(ε,φ)-expander decomposition of a graph G=(V,E) is a clustering of the vertices V=V1∪…∪ Vx such that (1) each cluster Vi induces subgraph with conductance at least φ, and (2) the number of inter-cluster edges is at most ε|E|. In this paper, we give an improved distributed expander decomposition, and obtain a nearly optimal distributed triangle enumeration algorithm in the CONGEST model.

We study the problem of graph clustering where the goal is to partition a graph into clusters, i.e. disjoint subsets of vertices, such that each cluster is well connected internally while sparsely connected to the rest of the graph. In particular, we use a natural bicriteria notion motivated by Kannan, Vempala, and Vetta [27] which we refer to as expander decomposition. Expander decomposition has become one of the building blocks in the design of fast graph algorithms, most notably in the nearly linear time Laplacian solver by Spielman and Teng [48], and it also has wide applications in practice. We design algorithm for the parametrized version of expander decomposition, where given a graph G of m edges and a parameter ϕ, our algorithm finds a partition of the vertices into clusters such that each cluster induces a subgraph of conductance at least ϕ (i.e. a ϕ expander), and only a Õ(ϕ) fraction of the edges in G have endpoints across different clusters. Our algorithm runs in Õ(m/ϕ) time, and is the first nearly linear time algorithm when ϕ is at least 1/logO(1) m, which is the case in most practical settings and theoretical applications. Previous results either take Ω(m1+o(1)) time (e.g. [34, 54]), or attain nearly linear time but with a weaker expansion guarantee where each output cluster is guaranteed to be contained inside some unknown b expander (e.g. [50, 2]). Our result achieve both nearly linear running time and the strong expander guarantee for clusters. Moreover, a main technique we develop for our result can be applied to obtain a much better expander pruning algorithm, which is the key tool for maintaining an expander decomposition on dynamic graphs. Finally, we note that our algorithm is developed from first principles based on relatively simple and basic techniques, thus making it very likely to be practical.

We present the first sublinear-time algorithm that can compute the edge connectivity λ of a network exactly on distributed message-passing networks (the CONGEST model), as long as the network contains no multi-edge. We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity λ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes Õ(n1−1/353D1/353+n1−1/706) time to compute λ and a cut of cardinality λ with high probability, where n and D are the number of nodes and the diameter of the network, respectively, and Õ hides polylogarithmic factors. This running time is sublinear in n (i.e. Õ(n1−є)) whenever D is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when λ=O(n1/8−є) [Thurimella PODC’95; Pritchard, Thurimella, ACM Trans. Algorithms’11; Nanongkai, Su, DISC’14] or (ii) approximately [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]. To achieve this we develop and combine several new techniques. First, we design the first distributed algorithm that can compute a k-edge connectivity certificate for any k=O(n1−є) in time Õ(√nk+D). The previous sublinear-time algorithm can do so only when k=o(√n) [Thurimella PODC’95]. In fact, our algorithm can be turned into the first parallel algorithm with polylogarithmic depth and near-linear work. Previous near-linear work algorithms are essentially sequential and previous polylogarithmic-depth algorithms require Ω(mk) work in the worst case (e.g. [Karger, Motwani, STOC’93]). Second, we show that by combining the recent distributed expander decomposition technique of [Chang, Pettie, Zhang, SODA’19] with techniques from the sequential deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC’15], we can decompose the network into a sublinear number of clusters with small average diameter and without any mincut separating a cluster (except the “trivial” ones). This leads to a simplification of the Kawarabayashi-Thorup framework (except that we are randomized while they are deterministic). This might make this framework more useful in other models of computation. Finally, by extending the tree packing technique from [Karger STOC’96], we can find the minimum cut in time proportional to the number of components. As a byproduct of this technique, we obtain an Õ(n)-time algorithm for computing exact minimum cut for weighted graphs.

Vertex connectivity a classic extensively-studied problem. Given an integer k, its goal is to decide if an n-node m-edge graph can be disconnected by removing k vertices. Although a linear-time algorithm was postulated since 1974 [Aho, Hopcroft and Ullman], and despite its sibling problem of edge connectivity being resolved over two decades ago [Karger STOC’96], so far no vertex connectivity algorithms are faster than O(n2) time even for k=4 and m=O(n). In the simplest case where m=O(n) and k=O(1), the O(n2) bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory’69]. For higher m, O(m) time is known for k≤ 3 [Tarjan FOCS’71; Hopcroft, Tarjan SICOMP’73], the first O(n2) time is from [Kanevsky, Ramachandran, FOCS’87] for k=4 and from [Nagamochi, Ibaraki, Algorithmica’92] for k=O(1). For general k and m, the best bound is Õ(min(kn2, nω+nkω)) [Henzinger, Rao, Gabow FOCS’96; Linial, Lovász, Wigderson FOCS’86] where Õ hides polylogarithmic terms and ω<2.38 is the matrix multiplication exponent.

Does there exist O(1)-competitive (self-adjusting) binary search tree (BST) algorithms? This is a well-studied problem. A simple offline BST algorithm GreedyFuture was proposed independently by Lucas and Munro, and they conjectured it to be O(1)-competitive. Recently, Demaine et al. gave a geometric view of the BST problem. This view allowed them to give an online algorithm GreedyArb with the same cost as GreedyFuture. However, no o(n)-competitive ratio was known for GreedyArb. In this paper we make progress towards proving O(1)-competitive ratio for GreedyArb by showing that it is O(\log n)-competitive.

We study computing all-pairs shortest paths (APSP) on distributed networks (the CONGEST model). The goal is for every node in the (weighted) network to know the distance from every other node using communication. The problem admits (1+o(1))-approximation Õ(n)-time algorithms [2], [3], which are matched with Ω(n)-time lower bounds [3], [4], [5]1. No ω(n) lower bound or o(m) upper bound were known for exact computation. In this paper, we present an Õ(n5/4)-time randomized (Las Vegas) algorithm for exact weighted APSP; this provides the first improvement over the naive O(m)-time algorithm when the network is not so sparse. Our result also holds for the case where edge weights are asymmetric (a.k.a. the directed case where communication is bidirectional). Our techniques also yield an Õ(n3/4k1/2+ n)-time algorithm for the k-source shortest paths problem where we want every node to know distances from k sources; this improves Elkin's recent bound [6] when k = ω̃(n1/4). We achieve the above results by developing distributed algorithms on top of the classic scaling technique, which we believe is used for the first time for distributed shortest paths computation. One new algorithm which might be of an independent interest is for the reversed r-sink shortest paths problem, where we want every of r sinks to know its distances from all other nodes, given that every node already knows its distance to every sink. We show an Õ(n√r)-time algorithm for this problem. Another new algorithm is called short range extension, where we show that in Õ(n√h) time the knowledge about distances can be “extended” for additional h hops. For this, we use weight rounding to introduce small additive errors which can be later fixed.

We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our algorithm guarantees an O(no(1)) worst-case update time with high probability. This significantly improves the two recent Las Vegas algorithms by Wulff-Nilsen [2] with update time O(n0.5-ε) for some constant ε > 0 and, independently, by Nanongkai and Saranurak [3] with update time O(n0.494) (the latter works only for maintaining a spanning forest). Our result is obtained by identifying the common framework that both two previous algorithms rely on, and then improve and combine the ideas from both works. There are two main algorithmic components of the framework that are newly improved and critical for obtaining our result. First, we improve the update time from O(n0.5-ε) in [2] to O(no(1)) for decrementally removing all low-conductance cuts in an expander undergoing edge deletions. Second, by revisiting the “contraction technique” by Henzinger and King [4] and Holm et al. [5], we show a new approach for maintaining a minimum spanning forest in connected graphs with very few (at most (1 + o(1))n) edges. This significantly improves the previous approach in [2], [3] which is based on Frederickson's 2-dimensional topology tree [6] and illustrates a new application to this old technique.

We present two algorithms for dynamically maintaining a spanning forest of a graph undergoing edge insertions and deletions. Our algorithms guarantee worst-case update time and work against an adaptive adversary, meaning that an edge update can depend on previous outputs of the algorithms. We provide the first polynomial improvement over the long-standing O(√n) bound of [Frederickson STOC'84, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] for such type of algorithms. The previously best improvement was O(√n (loglogn)2/logn) [Kejlberg-Rasmussen, Kopelowitz, Pettie and Thorup ESA'16]. We note however that these bounds were obtained by deterministic algorithms while our algorithms are randomized.

The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i.e. One that is constant factor competitive with any BST on any input access sequence. The two main candidates for dynamic optimality in the literature are splay trees [Sleator and Tarjan, 1985], and Greedy [Lucas, 1988, Munro, 2000, Demaine et al. 2009]. Despite BSTs being among the simplest data structures in computer science, and despite extensive effort over the past three decades, the conjecture remains elusive. Dynamic optimality is trivial for almost all sequences: the optimum access cost of most length-n sequences is Theta(n log n), achievable by any balanced BST. Thus, the obvious missing step towards the conjecture is an understanding of the "easy" access sequences, and indeed the most fruitful research direction so far has been the study of specific sequences, whose "easiness" is captured by a parameter of interest. For instance, splay provably achieves the bound of O(nd) when d roughly measures the distances between consecutive accesses (dynamic finger), the average entropy (static optimality), or the delays between multiple accesses of an element(working set). The difficulty of proving dynamic optimality is witnessed by other highly restricted special cases that remain unresolved, one prominent example is the traversal conjecture [Sleator and Tarjan, 1985], which states that preorder sequences (whose optimum is linear) are linear-time accessed by splay trees, no online BST is known to satisfy this conjecture. In this paper, we prove two different relaxations of the traversal conjecture for Greedy: (i) Greedy is almost linear for preorder traversal, (ii) if a linear-time preprocessing is allowed, Greedy is in fact linear. These statements are corollaries of our more general results that express the complexity of access sequences in terms of a pattern avoidance parameter k. Pattern avoidance is a well-established concept in combinatorics, and the classes of input sequences thus defined are rich, e.g. The k = 3 case includes preorder sequences. For any sequence X with parameter k, our most general result shows that Greedy achieves the cost n*2(Α(n))O(k) where Α is the inverse Ackermann function. Furthermore, a broad subclass of parameter-k sequences has a natural combinatorial interpretation as k-decomposable sequences. For this class of inputs, we obtain an n*2O(k) bound for Greedy when preprocessing is allowed. For k = 3, these results imply (i) and (ii). To our knowledge, these are the first upper bounds for Greedy that are not known to hold for any other online BST. To obtain these results we identify an input-revealing property of Greedy. Informally, this means that the execution log partially reveals the structure of the access sequence. This property facilitates the use of rich technical tools from forbidden sub matrix theory. Further studying the intrinsic complexity of k-decomposable sequences, we make several observations. First, in order to obtain an offline optimal BST, it is enough to bound Greedy on non-decomposable access sequences. Furthermore, we show that the optimal cost for k-decomposable sequences is Theta(n log k), which is well below the proven performance of all known BST algorithms. Hence, sequences in this class can be seen as a "candidate counterexample" to dynamic optimality.

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v1, ..., vn, one by one. After seeing each vector vi, we have to output the product Mvi before we can see the next vector. A naive algorithm can solve this problem using O(n3) time in total, and its running time can be slightly improved to O(n3/log2 n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (O(n3-ε)) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "Strassen-like algorithms" [Ballard et al. SPAA'11].