We study the directed global minimum vertex-cut problem: given a directed vertex-weighted graph \(G\), compute a vertex-cut \((L, S, R)\) in \(G\) of minimum value, which is defined to be the total weight of all vertices in \(S\). The problem, together with its edge-based variant, is one of the most basic in graph theory and algorithms, and has been studied extensively. The fastest currently known algorithm for directed global minimum vertex-cut (Henzinger, Rao and Gabow, FOCS 1996 and J. Algorithms 2000) has running time \(\tilde{O}(mn)\), where \(m\) and \(n\) denote the number of edges and vertices in the input graph, respectively. A long line of work over the past decades led to faster algorithms for other main versions of the problem, including the undirected edge-based setting (Karger, STOC 1996 and J. ACM 2000), directed edge-based setting (Cen et al., FOCS 2021), and undirected vertex-based setting (Chuzhoy and Trabelsi, STOC 2025). However, for the vertex-based version in directed graphs, the 29 year-old \(\tilde{O}(mn)\)-time algorithm of Henzinger, Rao and Gabow remains the state of the art to this day, in all edge-density regimes.

The All-Pairs Max-Flow problem has gained significant popularity in the last two decades, and many results are known regarding its fine-grained complexity. Despite this, wide gaps remain in our understanding of the time complexity for several basic variants of the problem, including for directed or undirected input graphs that are edge- or node-capacitated, and where the capacities are unit or arbitrary. In this paper, we aim to bridge this gap by providing algorithms, conditional lower bounds, and non-reducibility results. Notably, we show that for most problem settings, deterministic reductions based on the Strong Exponential Time Hypothesis O (n 4-ε) time algorithms for some smal 1 constant ε > 0, under a hypothesis called NSETH.

A classic 1993 paper by Althöfer et al. proved a tight reduction from spanners, emulators, and distance oracles to the extremal function $\gamma$ of high-girth graphs. This paper initiated a large body of work in network design, in which problems are attacked by reduction to $\gamma$ or the analogous extremal function for other girth concepts. In this paper, we introduce and study a new girth concept that we call the bridge girth of path systems, and we show that it can be used to significantly expand and improve this web of connections between girth problems and network design. We prove two kinds of results:•We write the maximum possible size of an n-node, p-path system with bridge girth $\gt k$ as $\beta(n, p, k)$, and we write a certain variant for “ordered” path systems as $\beta^{*}(n, p, k)$. We identify several arguments in the literature that implicitly show upper or lower bounds on $\beta, \beta^{*}$, and we provide some polynomial improvements to these bounds. In particular, we construct a tight lower bound for $\beta(n, p, 2)$, and we polynomially improve the upper bounds for $\beta(n, p, 4)$ and $\beta^{*}(n, p, \infty)$.•We show that many state-of-the-art results in network design can be recovered or improved via black-box reductions to $\beta$ or $\beta^{*}$. Examples include bounds for distance/reachability preservers, exact hopsets, shortcut sets, the flow-cut gaps for directed multicut and sparsest cut, an integrality gap for directed Steiner forest.We believe that the concept of bridge girth can lead to a stronger and more organized map of the research area. Towards this, we leave many open problems related to both bridge girth reductions and extremal bounds on the size of path systems with high bridge girth.

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 devise new cut sparsifiers that are related to the classical sparsification of Nagamochi and Ibaraki [Algorithmica, 1992], which is an algorithm that, given an unweighted graph G on n nodes and a parameter k, computes a subgraph with O(nk) edges that preserves all cuts of value up to k. We put forward the notion of a friendly cut sparsifier, which is a minor of G that preserves all friendly cuts of value up to k, where a cut in G is called friendly if every node has more edges connecting it to its own side of the cut than to the other side. We present an algorithm that, given a simple graph G, computes in almost-linear time a friendly cut sparsifier with edges. Using similar techniques, we also show how, given in addition a terminal set T, one can compute in almost-linear time a terminal sparsifier, which preserves the minimum st-cut between every pair of terminals, with edges. Plugging these sparsifiers into the recent n2+o(1)-time algorithms for constructing a Gomory-Hu tree of simple graphs, along with a relatively simple procedure for handling the unfriendly minimum cuts, we improve the running time for moderately dense graphs (e.g., with m = n1.75 edges). In particular, assuming a linear-time Max-Flow algorithm, the new state-of-the-art for Gomory-Hu tree is the minimum between our (m + n1.75)1+o(1) and the known mn1/2+o(1). We further investigate the limits of this approach and the possibility of better sparsification. Under the hypothesis that an Õ(n)-edge sparsifier that preserves all friendly minimum st-cuts can be computed efficiently, our upper bound improves to Õ(m + n1.5) which is the best possible without breaking the cubic barrier for constructing Gomory-Hu trees in non-simple graphs.

We design an$n^{2+o(1)}$-time algorithm that constructs a cut-equivalent (Gomory-Hu) tree of a simple graph on$n$nodes. This bound is almost-optimal in terms of$n$, and it improves on the recent$\tilde{O}(n^{2.5})$bound by the authors (STOC 2021), which was the first to break the cubic barrier. Consequently, the All-Pairs Maximum-Flow (APMF) problem has time complexity$n^{2+o(1)}$, and for the first time in history, this problem can be solved faster than All-Pairs Shortest Paths (APSP). We further observe that an almost-linear time algorithm (in terms of the number of edges$m$) is not possible without first obtaining a subcubic algorithm for multigraphs. Finally, we derandomize our algorithm, obtaining the first subcubic deterministic algorithm for Gomory-Hu Tree in simple graphs, showing that randomness is not necessary for beating the$n-1$times max-flow bound from 1961. The upper bound is$\tilde{O}(n^{2\frac{2}{3}})$and it would improve to$n^{2+o(1)}\ \mathbf{i}\mathbf{f}$there is a deterministic single-pair maximum-flow algorithm that is almost-linear. The key novelty is in using a “dynamic pivot” technique instead of the randomized pivot selection that was central in recent works.

Every undirected graph G has a (weighted) cut-equivalent tree T, commonly named after Gomory and Hu who discovered it in 1961. Both T and G have the same node set, and for every node pair s,t, the minimum (s,t)-cut in T is also an exact minimum (s,t)-cut in G.

Min-Cut queries are fundamental: Preprocess an undirected edge-weighted graph, to quickly report a minimum-weight cut that separates a query pair of nodes s, t. The best data structure known for this problem simply builds a cut-equivalent tree, discovered 60 years ago by Gomory and Hu, who also showed how to construct it using n-1 minimum st-cut computations. Using state-of-the-art algorithms for minimum st-cut (Lee and Sidford, FOCS 2014), one can construct the tree in time ~O(mn3/2), which is also the preprocessing time of the data structure. (Throughout, we focus on polynomially-bounded edge weights, noting that faster algorithms are known for small/ u nit edge weights, and use n and m for the number of nodes and edges in the graph.) Our main result shows the following equivalence: Cut-equivalent trees can be constructed in near-linear time if and only if there is a data structure for Min-Cut queries with near-linear preprocessing time and polylogarithmic (amortized) query time, and even if the queries are restricted to a fixed source. That is, equivalent trees are an essentially optimal solution for Min-Cut queries. This equivalence holds even for every minor-closed family of graphs, such as bounded-treewidth graphs, for which a two-decade old data structure (Arikati, Chaudhuri, and Zaroliagis, J. Algorithms 1998) implies the first near-linear time construction of cut-equivalent trees. Moreover, unlike all previous techniques for constructing cut-equivalent trees, ours is robust to relying on approximation algorithms. In particular, using the almost-linear time algorithm for ( 1+ε)-approximate minimum st-cut (Kelner, Lee, Orecchia, and Sidford, SODA 2014), we can construct a ( 1+ε)-approximate flow-equivalent tree (which is a slightly weaker notion) in time n2+o(1). This leads to the first ( 1+ε)-approximation for All-Pairs Max-Flow that runs in time n2+o(1), and matches the output size almost-optimally.

We investigate the time-complexity of the All-Pairs Max-Flow problem: Given a graph with n nodes and m edges, compute for all pairs of nodes the maximum-flow value between them. If Max-Flow (the version with a given source-sink pair s, t) can be solved in time T(m), then an O(n2) · T(m) is a trivial upper bound. But can we do better? For directed graphs, recent results in fine-grained complexity suggest that this time bound is essentially optimal. In contrast, for undirected graphs with edge capacities, a seminal algorithm of Gomory and Hu (1961) runs in much faster time O(n) • T(m). Under the plausible assumption that Max-Flow can be solved in near-linear time m1+o(1), this half-century old algorithm yields an nm1+o(1) bound. Several other algorithms have been designed through the years, including Õ(mn) time for unit-capacity edges (unconditionally), but none of them break the O(mn) barrier. Meanwhile, no super-linear lower bound was shown for undirected graphs. We design the first hardness reductions for All-Pairs Max-Flow in undirected graphs, giving an essentially optimal lower bound for the node-capacities setting. For edge capacities, our efforts to prove similar lower bounds have failed, but we have discovered a surprising new algorithm that breaks the O(mn) barrier for graphs with unit-capacity edges! Assuming T(m) = m1+o(1), our algorithm runs in time m3/2+o(1) and outputs a cut-equivalent tree (similarly to the Gomory-Hu algorithm). Even with current Max-Flow algorithms we improve state-of-the-art as long as m = O(n5/3−ε). Finally, we explain the lack of lower bounds by proving a non-reducibility result. This result is based on a new quasi-linear time Õ(m) non-deterministic algorithm for constructing a cut-equivalent tree and may be of independent interest.

The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum s-t cut (or just its value) for all pairs of vertices s, t. We study this problem in directed graphs with unit edge/vertex capacities (corresponding to edge/vertex connectivity). Our focus is on the k-bounded case, where the algorithm has to find all pairs with min-cut value less than k, and report only those. The most basic case k = 1 is the Transitive Closure (TC) problem, which can be solved in graphs with n vertices and m edges in time O(mn) combinatorially, and in time O(nω) where ω < 2.38 is the matrix-multiplication exponent. These time bounds are conjectured to be optimal. We present new algorithms and conditional lower bounds that advance the frontier for larger k, as follows: A randomized algorithm for vertex capacities that runs in time O((nk)ω). This is only a factor kω away from the TC bound, and nearly matches it for all k = no(1). Two deterministic algorithms for edge capacities (which is more general) that work in DAGs and further reports a minimum cut for each pair. The first algorithm is combinatorial (does not involve matrix multiplication) and runs in time O(2O(k2) · mn). The second algorithm can be faster on dense DAGs and runs in time O((k log n)4k+o(k) · nω). Previously, Georgiadis et al. [ICALP 2017], could match the TC bound (up to no(1) factors) only when k = 2, and now our two algorithms match it for all k = o(√log n) and k = o(log log n). The first super-cubic lower bound of nω−1−o(1)k2 time under the 4-Clique conjecture, which holds even in the simplest case of DAGs with unit vertex capacities. It improves on the previous (SETH-based) lower bounds even in the unbounded setting k = n. For combinatorial algorithms, our reduction implies an n2−o(1)k2 conditional lower bound. Thus, we identify new settings where the complexity of the problem is (conditionally) higher than that of TC. Our three sets of results are obtained via different techniques. The first one adapts the network coding method of Cheung, Lau, and Leung [SICOMP 2013] to vertex-capacitated digraphs. The second set exploits new insights on the structure of latest cuts together with suitable algebraic tools. The lower bounds arise from a novel reduction of a different structure than the SETH-based constructions.

In the Set Cover problem, the input is a ground set of $n$ elements and a collection of $m$ sets, and the goal is to find the smallest sub-collection of sets whose union is the entire ground set. The fastest algorithm known runs in time $O(mn2^n)$ [Fomin et al., WG 2004], and the Set Cover Conjecture (SeCoCo) [Cygan et al., TALG 2016] asserts that for every fixed $\varepsilon>0$, no algorithm can solve Set Cover in time $2^{(1-\varepsilon)n}poly(m)$, even if set sizes are bounded by $Δ=Δ(\varepsilon)$. We show strong connections between this problem and kTree, a special case of Subgraph Isomorphism where the input is an $n$-node graph $G$ and a $k$-node tree $T$, and the goal is to determine whether $G$ has a subgraph isomorphic to $T$. First, we propose a weaker conjecture Log-SeCoCo, that allows input sets of size $Δ=O(1/\varepsilon \cdot\log n)$, and show that an algorithm breaking Log-SeCoCo would imply a faster algorithm than the currently known $2^n poly(n)$-time algorithm [Koutis and Williams, TALG 2016] for Directed nTree, which is kTree with $k=n$ and arbitrary directions to the edges of $G$ and $T$. This would also improve the running time for Directed Hamiltonicity, for which no algorithm significantly faster than $2^n poly(n)$ is known despite extensive research. Second, we prove that if Set Cover cannot be solved significantly faster than $2^npoly(m)$ (an assumption even weaker than Log-SeCoCo), then kTree cannot be computed significantly faster than $2^kpoly(n)$, the running time of the Koutis and Williams' algorithm. Applying the same techniques to the p-Partial Cover problem, a parameterized version of Set Cover that requires covering at least $p$ elements, we obtain a new algorithm with running time $(2+\varepsilon)^p (m+n)^{O(1/\varepsilon)}$ for arbitrary $\varepsilon>0$, which improves previous work and is nearly optimal assuming say Log-SeCoCo.

We provide evidence that computing the maximum flow value between every pair of nodes in a directed graph on n nodes, m edges, and capacities in the range [1‥ n ], which we call the All-Pairs Max-Flow problem, cannot be solved in time that is significantly faster (i.e., by a polynomial factor) than O ( n 3 ) even for sparse graphs, namely m = O ( n ); thus for general m , it cannot be solved significantly faster than O ( n 2 m ). Since a single maximum st -flow can be solved in time Õ( m √ n ) [Lee and Sidford, FOCS 2014], we conclude that the all-pairs version might require time equivalent to Ω ˜ ( n 3/2 ) computations of maximum st -flow, which strongly separates the directed case from the undirected one. Moreover, if maximum st -flow can be solved in time Õ( m ), then the runtime of Ω ˜ ( n 2 ) computations is needed. This is in contrast to a conjecture of Lacki, Nussbaum, Sankowski, and Wulff-Nilsen [FOCS 2012] that All-Pairs Max-Flow in general graphs can be solved faster than the time of O ( n 2 ) computations of maximum st -flow. Specifically, we show that in sparse graphs G = ( V , E , w ), if one can compute the maximum st -flow from every s in an input set of sources S ⊆ V to every t in an input set of sinks T ⊆ V in time O ((| S || T | m ) 1−ε ), for some | S |, | T | and a constant ε > 0, then MAX-CNF-SAT (maximum satisfiability of conjunctive normal form formulas) with n ′ variables and m ′ clauses can be solved in time m ′ O (1) 2 (1−δ) n ′ for a constant δ(ε) > 0, a problem for which not even 2 n ′ / poly ( n ′) algorithms are known. Such running time for MAX-CNF-SAT would in particular refute the Strong Exponential Time Hypothesis (SETH). Hence, we improve the lower bound of Abboud, Vassilevska-Williams, and Yu [STOC 2015], who showed that for every fixed ε > 0 and | S | = | T | = O (√ n ), if the above problem can be solved in time O ( n 3/2−ε ), then some incomparable (and intuitively weaker) conjecture is false. Furthermore, a larger lower bound than ours implies strictly super-linear time for maximum st -flow problem, which would be an amazing breakthrough. In addition, we show that All-Pairs Max-Flow in uncapacitated networks with every edge-density m = m ( n ) cannot be computed in time significantly faster than O ( mn ), even for acyclic networks. The gap to the fastest known algorithm by Cheung, Lau, and Leung [FOCS 2011] is a factor of O ( m ω−1 / n ), and for acyclic networks it is O ( n ω−1 ), where ω is the matrix multiplication exponent. Finally, we extend our lower bounds to the version that asks only for the maximum-flow values below a given threshold (over all source-sink pairs).