Authors Amir Abboud, Robert Krauthgamer, Ohad Trabelsi,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27
www.theoryofcomputing.org
New Algorithms and Lower Bounds for
All-Pairs Max-Flow in Undirected Graphs
Amir Abboud Robert Krauthgamer Ohad Trabelsi
Received December 19, 2019; Revised August 29, 2020; Published September 20, 2021
Abstract. 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 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 O(mn)
e time for unit-capacity edges (unconditionally),
but none of them break the O(mn) barrier. Meanwhile, no super-linear lower bound is known
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
A conference version of this paper appeared in the Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms
(SODA’20) [4].
ACM Classification: F.2.2, G.1.6
AMS Classification: 68W25
Key words and phrases: Gomory–Hu tree, conditional lower bounds, max-flow
© 2021 Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2021.v017a005
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
(similarly to the Gomory–Hu algorithm). Even with current Max-Flow algorithms we
improve the 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 near-linear
time O(m)
e nondeterministic algorithm for constructing a cut-equivalent tree and may be of
independent interest.
1 Introduction
In the maximum st-flow problem (abbreviated Max-Flow), the goal is to compute the maximum value
of a feasible flow between a given pair of nodes s,t (sometimes called terminals) in an input graph.1
Determining the time complexity of this problem is one of the most prominent open questions in fine-
grained complexity and algorithms. The best running time known for directed (or undirected) graphs
with n nodes, m edges, and largest integer capacity U is O(min{me 10/7U 1/7 , m11/8U 1/4 , m√n logU})
[39, 38, 36], where O(e f ) hides logarithmic factors and stands for O( f logO(1) f ). To date, there is no
Ω(m1+ε ) lower bound for this problem, even when utilizing one of the popular conjectures of fine-grained
complexity, such as the Strong Exponential-Time Hypothesis (SETH) of [31].2 This gap is debated
among experts, and a common belief is that such a lower bound is not possible, since a near-linear-time
algorithm should exist. There is also a formal barrier for basing a lower bound for Max-Flow on SETH,
as it would refute the so-called Nondeterministic SETH (NSETH) [16]. We will henceforth assume
that Max-Flow can be solved in time m1+o(1) , and investigate some of the most important questions that
remain open under this favorable assumption. (None of our results require this assumption; it only serves
to highlight their significance.)
Perhaps the most natural next step after the s,t version is the “all-pairs” version (abbreviated All-Pairs
Max-Flow), where the goal is to solve Max-Flow for all pairs of nodes in the graph. This multi-terminal
problem, dating back to 1960 [40, 18], is the main focus of our work:
What is the time complexity of computing Max-Flow between all pairs of nodes?
We will discuss a few natural settings, e. g., directed vs. undirected, or node capacities vs. edge
capacities, in which the answer to this question may vary. A trivial strategy for solving this problem (in
any setting) is to invoke a T (m)-time algorithm for the s,t version O(n2 ) times, giving a total time bound
of O(n2 ) · T (m), which is n2 · m1+o(1) under our favorable assumption. But one would hope to do much
better, as this all-pairs version arises in countless applications, such as a graph-clustering approach for
image segmentation [47].
In undirected edge-capacitated graphs, a seminal paper of Gomory and Hu [26] showed in 1961 how
to solve All-Pairs Max-Flow using only n − 1 calls to a Max-Flow algorithm, rather than O(n2 ) calls,
yielding an upper bound O(n) · T (m). (See also [28] for a different algorithm where all the n − 1 calls
can be executed on the original graph.) This time bound has improved over the years, following the
improvements in algorithms for Max-Flow, and under our assumption it would ultimately be n · m1+o(1) .
1 Throughout, we focus on computing the value of the flow (rather than an actual flow), which is equal to the value of the
minimum st-cut by the famous max-flow/min-cut theorem [21].
2 SETH asserts that for every fixed ε > 0 there is an integer k ≥ 3, such that kSAT on n variables and m clauses cannot be
solved in time 2(1−ε)n mO(1) .
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 2
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
Even more surprisingly, Gomory and Hu showed that all the n2 answers can be represented using a single
tree, which can be constructed in the same time bound. Formally, a cut-equivalent tree to a graph G is
an edge-capacitated tree T on the same set of nodes, with the property that for every pair of nodes s,t,
every minimum st-cut in T yields a bipartition of the nodes which is a minimum st-cut in G, and of the
same value as in T .3 See also [25] for an experimental study, and the Encyclopedia of Algorithms [43]
for more background. The only algorithm that constructs a cut-equivalent tree without making Ω(n) calls
to a Max-Flow algorithm was designed by Bhalgat, Hariharan, Kavitha, and Panigrahi [13]. It runs in
time O(mn)
e in unit-capacity graphs (or equivalently, if all edges have the same capacity), and utilizes
a tree-packing approach that was developed in [19, 29], inspired by classical results of [22] and [20].
However, if Max-Flow can indeed be computed in near-linear time, then none of the later algorithms beat
by a polynomial factor the time bound n · m1+o(1) of Gomory and Hu’s half-century old algorithm.
The time complexity of All-Pairs Max-Flow becomes higher in settings where Gomory and Hu’s “tree
structure” [26] does not hold. For instance, in node-capacitated graphs (where the flow is constrained at
intermediate nodes,4 rather than edges) flow-equivalent trees are impossible, since there could actually
exist Ω(n2 ) different maximum-flow values in a single graph [30] (see therein also an interesting
exposition of certain false claims made earlier). Directed edges make the all-pairs problem even harder;
in fact, in this case node capacities and edge capacities are equivalent, and thus this setting does not
admit flow-equivalent trees, see [41, 32, 30]. In the last decade, different algorithms were proposed
to beat the trivial O(n2 ) · T (m) time bound in these harder cases. The known bound for unit-capacity
graphs is O(mω ), due to Cheung, Lau, and Leung [17], where ω < 2.38 is the matrix multiplication
exponent. A related version, which is obviously no harder than All-Pairs Max-Flow, is to ask (among
all pairs of nodes) only for flow values that are at most k, assuming unit node-capacities; for example,
e ω )-time algorithm was
the case k = 1 is the transitive closure problem (reachability). For k = 2, an O(n
shown in [24], and very recently a similar bound was achieved for all k = O(1) [3]. The aforementioned
papers [17, 24, 3] also present improved algorithms for acyclic graphs (DAGs). In addition, essentially
e 2 ) algorithms were found for All-Pairs Max-Flow in certain graph families, including small
optimal O(n
treewidth [11], planar graphs [35], and surface-embedded graphs [14].
The framework of fine-grained complexity has been applied to the all-pairs problem in a few recent
papers, although its success has been limited to the directed case. Abboud, Vassilevska-Williams, and
Yu [8] proved SETH-based lower bounds for some multi-terminal variants of Max-Flow, such as the
single-source all-sinks version, but not all-pairs. Krauthgamer and Trabelsi [33] proved that All-Pairs
Max-Flow cannot be solved in time O(n3−ε ), for any fixed ε > 0, unless SETH is false, even in the sparse
regime m = n1+o(1) . This holds also for unit-capacity graphs, and it essentially settles the complexity
of the problem for directed sparse graphs, showing that the O(n2 ) · T (m) upper bound is optimal if one
assumes that T (m) = m1+o(1) . Recently, Abboud et al. [3] proved a conditional lower bound that is even
higher for dense graphs, showing that an O(nω+1−ε )-time algorithm would refute the 4-Clique conjecture.
3 Notice that a minimum st-cut in T consists of a single edge that has minimum capacity along the unique st-path in T , and
removing this edge disconnects T to two connected components. A flow-equivalent tree has the weaker property that for every
pair of nodes s,t, the maximum st-flow value in T equals that in G. The key difference is that flow-equivalence maintains only
the values of the flows (and thus also of the corresponding cuts).
4 Granot and Hassin [27] considered a related but different notion of minimum st-cuts with node capacities, where the flow is
constrained also by the capacities of the source and sink (in addition to the intermediate nodes), and so an equivalent tree exists
and can be computed efficiently. This makes the problem much easier.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 3
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
However, no non-trivial lower bound is known for undirected graphs.
1.1 The challenge of lower bounds in undirected graphs
Let us briefly explain the difficulty in obtaining lower bounds for undirected graphs. Consider the
following folklore reduction from Boolean Matrix Multiplication (BMM) to All-Pairs Reachability in
directed graphs (the aforementioned special case of All-Pairs Max-Flow with k = 1). In BMM the input
is two n × n Boolean matrices P and Q, and the goal is to compute the product matrix R given by
n
_
R(a, c) := P(a, b) ∧ Q(b, c) , ∀a, c ∈ [n].
b=1
Computing R can be reduced to All-Pairs Reachability as follows. Construct a graph with three layers
A, B,C with n nodes each, where the edges are directed A → B → C and represent the two matrices: a ∈ A
is connected to b ∈ B iff P(a, b) = 1; and b ∈ B is connected to c ∈ C iff Q(b, c) = 1. It is easy to see that
R(a, c) = 1 iff node a ∈ A can reach node c ∈ C (via a two-hop path).
This simple reduction shows an nω−o(1) lower bound for All-Pairs Reachability in dense directed
graphs assuming the BMM conjecture (see [7]), which states that any combinatorial algorithm (i. e.,
one that does not use fast matrix multiplication techniques) that solves BMM requires n3−o(1) time.
Higher lower bounds can be proved by more involved reductions that utilize the extra power of flow over
reachability, e. g., an n3−o(1) lower bound in sparse directed graphs assuming SETH [33]. Nevertheless,
this simple reduction illustrates the main difficulty in adapting such reductions to undirected graphs.
Consider the same construction but with undirected edges (i. e., without the edge orientations). The
main issue is that paths from A to C can now have more than two hops—they can crisscross between two
adjacent layers before moving on to the next one. Indeed, it is easy to construct examples in which the
product R(a, c) = 0 but there is a path from a to c (with more than two hops). Even if we try to use the
extra power of flow, giving us information about the number of paths rather than just the existence of a
path, it is still unclear how to distinguish flow that uses a two-hop path (YES case) from flow that uses
only longer paths (NO case).
A main technical novelty of this work is a trick to overcome this issue. The high-level idea is to
design large gaps between the capacities of nodes in different layers in order to incentivize flow to move
to the “next layer.” Let us exhibit how this trick applies to the simple reduction above. Remove the edge
orientations from our three-layer graph, and introduce node capacities, letting all nodes in B, the middle
layer, have capacity 2n, and all nodes in A ∪C, the other two layers, have capacity 1. Now, consider the
maximum flow from a ∈ A to c ∈ C. If R(a, c) = 1 then there is a two-hop path through some b ∈ B, which
can carry 2n units of flow, hence the maximum-flow value is at least 2n. On the other hand, if R(a, c) = 0
then every path from a to c must have at least four hops, and a maximum flow must be composed of such
paths. Any such path must pass through at least one node in A ∪ C \ {a, c}, whose capacity is only 1,
hence the maximum flow is bounded by |A ∪C \ {a, c}| = 2n − 2. This proves the same nω−o(1) lower
bound as before, but now for undirected graphs with node capacities. We note that the argument for
undirected graphs can be simplified a bit if we allow nodes of capacity 0. In Section 4 we utilize this trick
in a more elaborate way to prove stronger lower bounds.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 4
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
1.2 Our results
Our main negative result is the first (conditional) lower bound for All-Pairs Max-Flow that holds in
undirected graphs. For sparse, node-capacitated graphs we are able to match the lower bound n3−o(1) that
was previously known only for directed graphs [33], and it also matches the hypothetical upper bound
n3+o(1) .
Theorem 1.1. Assuming SETH, no algorithm can solve All-Pairs Max-Flow in undirected graphs on n
nodes and O(n) edges with node capacities in [n2 ] in time O(n3−ε ) for some fixed ε > 0.
Our lower bound holds even under assumptions that are weaker than SETH (see Section 4), as we
reduce from the 3-Orthogonal-Vectors (3OV) problem. At a high level, it combines the trick described
above for overcoming the challenge in undirected graphs, with the previous reduction of [33] from 3OV
to the directed case. However, both of these ingredients have their own subtleties and fitting them together
requires adapting and tweaking them very carefully.
Following our Theorem 1.1, the largest remaining gap in our understanding of All-Pairs Max-Flow
concerns the most basic and fundamental setting: undirected graphs with edge capacities. What is the
time complexity of computing a cut-equivalent tree? The upper bound has essentially been stuck at
n · m1+o(1) for more than half a century, while we cannot even rule out a near-linear m1+o(1) running time.
To our great surprise, after a series of failed attempts at proving any lower bound, we have noticed a
simple way to design a new algorithm for computing cut-equivalent trees for graphs with unit capacities,
breaking the longstanding mn barrier!
Theorem 1.2. There is an algorithm that, given an undirected graph G with n nodes and m edges with unit
edge-capacities and parameter 1 ≤ d ≤ n, constructs a cut-equivalent tree in time O(mde + Φ(m, n, d)),
where
n m/d m/d o
Φ(m, n, d) = max ∑ T (m, n, Fi ) : F1 , . . . , Fm/d ≥ 0, ∑ Fi ≤ 2m
i=1 i=1
and T (m, n, F) is the time bound for Max-Flow on instances whose flow value is at most a F.
Using the current bound on T (m, n, F) we achieve running time O(me 3/2 n1/6 ), and under the plausible
hypothesis that T (m, n) = m1+o(1) our time bound becomes m3/2+o(1) . In the regime of sparse graphs
where m = O(n)e the previous best algorithm of Bhalgat et al. [13] had running time O(n e 2 ) whereas
we achieve O(ne 5/3 ), or conditionally n3/2+o(1) . In fact, we improve on their upper bound as long as
m = O(n 5/3−ε ). Clearly, this also leads to improved bounds for All-Pairs Max-Flow (with unit edge-
capacities), for which the best strategy known is to compute the tree and then extract the answers in time
O(n2 ).
Note added in proof. Subsequent work further improved the above bound. First, by employing the
e + n1.5 )-time Max-Flow algorithm [15], our framework immediately gives a better running
recent O(m
time O(min{m
e 3/2 n1/6 , mn3/4 + m3/2 }). Second, new algorithms were developed for simple graphs: it
has started with [6], and has culminated in running time n2+o(1) [5, 37], or a slightly faster O(n e 2)
conditionally on a linear-time Max-Flow algorithm [48], and an even better bound for sufficiently sparse
graphs min{m7/6 n1/2+o(1) , mn1/2+o(1) + m1/2 n5/4+o(1) } [37].
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 5
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
The main open question remains: Can we prove any super-linear lower bounds for the edge-capacitated
case in undirected graphs? Is there an m1+ε lower bound under SETH for constructing a cut-equivalent
tree? Perhaps surprisingly, we prove a strong barrier for the possibility of such a result.
We follow the non-reducibility framework of Carmosino et al. [16]. Intuitively, if problem A is
conjectured to remain hard for nondeterministic algorithms while problem B is known to become
significantly easier for such algorithms, then we should not expect a reduction from A to B to exist.
Such a reduction would allow the nondeterministic speedups for problem B to carry over to A. To
formalize this connection, Carmosino et al. introduce NSETH: the hypothesis that SETH holds against
co-nondeterministic algorithms. NSETH is plausible because it is not clear how a powerful prover could
convince a sub-2n -time verifier that a given CNF formula is not satisfiable. Moreover, it is known that
refuting NSETH would require new techniques since it would imply new circuit lower bounds. Then,
Carmosino et al. exhibited nondeterministic (and co-nondeterministic) speedups for problems such as
3-SUM and Max-Flow (using LP duality), showing that a reduction from SAT to these problems would
refute NSETH.
Our final result builds on Theorem 1.2 to design a near-linear time5 nondeterministic algorithm for
constructing a cut-equivalent tree. This algorithm can perform nondeterministic choices and in the end,
outputs either a correct cut-equivalent tree or “don’t know” (i. e., aborts), however we are guaranteed that
for every input graph there is at least one sequence of nondeterministic choices that leads to a correct
output. Our result could have applications in computation-delegation settings and may be of interest in
other contexts. In particular, since our nondeterministic witness can be constructed deterministically
efficiently, namely, in polynomial but super-linear time, it provides a potentially interesting certifying
algorithm [42, 9] (see [34] for a recent paper with a further discussion of the connections to fine-grained
complexity). Our final non-reducibility result is as follows.
Theorem 1.3. If for some ε > 0 there is a deterministic fine-grained reduction proving an Ω(m1+ε ) lower
bound under SETH for constructing a cut-equivalent tree of an undirected unit edge-capacitated graph
on m edges, then NSETH is false.
Our result (and this framework for non-reducibility) does not address the possibility of proving a
SETH based lower bound with a randomized fine-grained reduction. This is because NSETH does not
remain plausible when faced against randomization (see [16, 46]). That said, we are not aware of any
examples where this barrier has been bypassed with randomization.
Roadmap. Our main algorithm is described in the Section 2. The nondeterministic algorithm and
non-reducibility result are presented in Section 3. We then present our lower bounds in Section 4. The
last section discusses open questions.
2 Algorithm for a cut-equivalent tree
The basic strategy in our algorithm for unit edge-capacities is to handle separately nodes whose connectiv-
ity (to other nodes) is high from those whose connectivity is low. The motivation comes from the simple
5 We say that a time bound T (n) is near-linear if it is bounded by O(n logc n) for some constant c > 0.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 6
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
observation that the degree of a node is an upper bound on the maximum flow from this node to any other
node in the graph. Specifically, our algorithm has two stages. The first stage uses one method (of partial
trees [29, 13]), to compute the parts of the tree that correspond to small connectivities, and the second
stage uses another method (the classical Gomory–Hu algorithm [26]) to complete it to a cut-equivalent
tree (see Figure 1). Let us briefly review these two methods.
The Gomory–Hu algorithm. This algorithm constructs a cut-equivalent tree T in iterations. Initially,
T is a single node associated with V (the node set of G), and the execution maintains the invariant that T
is a tree; each tree node i is a super-node, which means that it is associated with a subset Vi ⊆ V ; and
these super-nodes form a partition V = V1 t · · · t Vl . At each iteration, the algorithm picks arbitrarily
two graph nodes s,t that lie in the same tree super-node i, i. e., s,t ∈ Vi . The algorithm then constructs
from G an auxiliary graph G0 by merging nodes that lie in the same connected component of T \ {i} and
invokes a Max-Flow algorithm to compute in this G0 a minimum st-cut, denoted C0 . (For example, if the
current tree is a path on super-nodes 1, . . . , l, then G0 is obtained from G by merging V1 ∪ · · · ∪Vi−1 into
one node and Vi+1 ∪ · · · ∪Vl into another node.) The submodularity of cuts ensures that this cut is also a
minimum st-cut in the original graph G, and it clearly induces a partition Vi = S t T with s ∈ S and t ∈ T .
The algorithm then modifies T by splitting super-node i into two super-nodes, one associated with S and
one with T , that are connected by an edge whose weight is the value of the cut C0 , and further connecting
each neighbor of i in T to either S or T (viewed as super-nodes), depending on its side in the minimum
st-cut C0 (more precisely, a neighbor j is connected to the side containing V j ).
𝑉𝑖 𝑆
𝑠 𝑠
Minimum-Cut value
𝑡 between 𝑠 and 𝑡 𝑡
𝑇
Figure 1: An illustration of the construction of T. Left: T right before the partition of the super-node Vi .
Middle: after the partitioning of Vi . Right: T as it unfolds after the Gomory–Hu algorithm finishes.
The algorithm performs these iterations until all super-nodes are singletons, and then T is a weighted
tree with effectively the same node set as G. It can be shown [26] that for every s,t ∈ V , the minimum
st-cut in T, viewed as a bipartition of V , is also a minimum st-cut in G, and of the same cut value. We
stress that this property holds regardless of the choice made at each step of two nodes s 6= t ∈ Vi .
Partial tree. A k-partial tree, formally defined below, can also be thought of as the result of contracting
all edges of weight greater than k in a cut-equivalent tree of G. Such a tree can obviously be constructed
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 7
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
using the Gomory–Hu algorithm, but as stated below (in Lemma 2.2), faster algorithms were designed
in [29, 13], see also [43, Theorem 3]. We show below (in Lemma 2.3) that such a tree can be obtained
also by a truncated execution of the Gomory–Hu algorithm, and finally we use this simple but crucial fact
to prove our main theorem.
Definition 2.1 (k-Partial Tree [29]). A k-partial tree of a graph G = (V, E) is a weighted tree on l ≤ |V |
super-nodes constituting a partition V = V1 t · · · tVl , with the following property: For every two nodes
s,t ∈ V whose minimum-cut value in G is at most k, s and t lie in different super-nodes s ∈ S and t ∈ T ,
such that the minimum ST -cut in the tree defines a bipartition of V which is a minimum st-cut in G and
has the same value.
Lemma 2.2 ([13]). There is an algorithm that given an undirected graph with n nodes and m edges with
unit edge-capacities and an integer k ∈ [n], constructs a k-partial tree in time O(mk).
e
Lemma 2.3. Given a k-partial tree Tlow of a graph G = (V, E), there is a truncated execution of the
Gomory–Hu algorithm that produces Tlow (i. e., its auxiliary tree T becomes Tlow ).
Proof. Consider an execution of the Gomory–Hu algorithm with the following choices. At each iteration,
pick any two nodes s,t ∈ V that lie in the same super-node i of the current tree T (hence they are feasible
choice in a Gomory–Hu execution) but furthermore lie in different super-nodes of Tlow , as long as such
s,t exist. Then split super-node i of T using the minimum st-cut induced by Tlow (rather than an arbitrary
minimum st-cut). As this cut corresponds to an edge in Tlow , it cannot split any super-node of Tlow , which
implies, by an inductive argument, that the super-nodes of Tlow are subsets of the super-nodes of T, and
thus our chosen cut is a feasible choice for a Gomory–Hu execution. In order to claim that T will have
the same tree structure as Tlow , we also use the following simple inductive argument. Each pair A, B of
super-nodes of T connected with an edge of capacity c has a pair A0 ⊆ A, B0 ⊆ B of super-nodes of Tlow
with an edge of capacity c between A0 and B0 in Tlow . Notice also that a pair s,t as required above can be
chosen as long as T is not equal to Tlow , and hence, together with the two inductive claims above, the
Gomory–Hu execution continues until T becomes exactly Tlow .
We are now ready to prove our main theorem.
Proof of Theorem 1.2. Let G = (V, E) be an input undirected graph with unit edge-capacities, and denote
by Vlow all the nodes in G whose degrees are at most the chosen parameter d ∈ [n], and by Vhigh = V \Vlow
the nodes whose degrees are greater than d.
First use Lemma 2.2 to construct a d-partial tree Tlow , and treat it as the auxiliary tree computed by a
truncated execution of the Gomory–Hu algorithm. Then continue a Gomory–Hu execution (using this
tree) to complete the construction of a cut-equivalent tree. Note that every node in Vlow is in a singleton
super-node of Tlow , since its minimum cut value to any other node is at most d; thus a super-node Vi in
Tlow has more than one node if and only if it contains only nodes in Vhigh . Moreover, by the properties of
Tlow , two nodes have minimum-cut value greater than d if and only if they are in the same super-node Vi .
Since by Lemma 2.3 there exists a truncated Gomory–Hu execution that produces Tlow , a Gomory–Hu
execution starting with Tlow as the auxiliary tree will result in a cut-equivalent tree and the correctness
follows. The running time bound follows as the first step of constructing Tlow takes O(md) e time, and
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 8
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
the second step of the Gomory–Hu execution takes |Vhigh | invocations of Max-Flow, that is running time
m/d
∑i=1 T (m, n, Fi ). Finally, we will use the following known claim regarding a bound on the total sum of
capacities of cut-equivalent trees.
Claim 2.4 (From Lemma 4 in [13]). Let G be a unit edge-capacity graph G and T its cut-equivalent tree.
Then the sum of capacities over all edges of T is bounded by 2m.
Now, since every invocation of maximum st-flow with value Fi in our algorithm determines a unique
edge with capacity Fi in the final cut-equivalent tree, and by Claim 2.4 the sum of the capacities over all
m/d
the edges of the cut-equivalent tree satisfies ∑i=1 Fi ≤ 2m, it holds that the total time spent on the m/d
invocations of Max-Flow is bounded by Φ(m, n, d). Thus, the proof of Theorem 1.2 is concluded.
e + m3/4 n1/4 F 1/2 ) time algorithm by [44] to optimize our running time.
We use the T (m, n, F) = O(m
m/d
By the concavity of F 1/2 , the maximum of ∑i=1 T (m, n, Fi ) is attained when all Fi = d. By setting
√ 1/6
d = mn we get
√ √
m/n1/6 m/n1/6
∑ (m + m3/4 n1/4 m1/4 n1/12 ) = ∑ mn1/3 = m3/2 n1/6 ,
i=1 i=1
which is faster than the known O(mn)-time
e algorithm of [13] whenever m ∈ [n, n5/3 ].
√
Finally, relying on a hypothetical m1+o(1) -time algorithm for Max-Flow, we could set d = m to
√ √
get a total running time of m1+o(1) · m/ m + O(m e · m) ≤ m3/2+o(1) , as claimed immediately after
Theorem 1.2.
3 Near-linear nondeterministic algorithm for cut-equivalent tree
As no conditional lower bounds are known for the problem of constructing a cut-equivalent tree, one
potentially promising approach is to design a reduction from SAT to prove that running time n1+δ −o(1) ,
for a fixed δ > 0, is not possible assuming SETH. However, in this section we show that the existence
of such a reduction (at least in the case of unit edge-capacities) would refute NSETH. This proves our
Theorem 1.3.
Our main technical result in this section (Theorem 3.2) is a fast nondeterministic algorithm for
constructing a cut-equivalent tree (the meaning of this notion will be formalized shortly). We then reach
the conclusion about NSETH by following an argument first made in [16], however we have to rewrite
their argument (rather than use their definitions and results directly), in order to adapt it from decision
problems or functions (where each input has exactly one output) to total search problems, since every
graph has at least one cut-equivalent tree (see Section 3.2).
Generally speaking, a search problem P is a binary relation, and we say that S is a solution to instance
x iff (x, S) ∈ P. Let SOL(x) = {S : (x, S) ∈ P} denote the set of solutions for instance x. We say that P
is a total search problem6 if every instance x has at least one solution, i. e., SOL(x) 6= 0./ Let ⊥ be the
“don’t know” symbol and assume that ⊥ ∈ / SOL(x) for all x. For example, in our problem of constructing
a cut-equivalent tree, x is a graph and SOL(x) is the set of all cut-equivalent trees for x.
6 In some of the previous literature it is called a total function, although it is actually a relation rather than a function.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 9
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
Definition 3.1 (Nondeterministic complexity of a total search problem). We say that a total search
problem P has nondeterministic time complexity T (n) if there is a deterministic Turing Machine M such
that for every instance x of P with size |x| = n:
1. ∀g, THALT (M(x, g)) ≤ T (n), i. e., the time complexity of M on input x with guess g is bounded by
T (n);
2. ∃g, M(x, g) ∈ SOL(x), i. e., at least one guess leads M to output a solution;
3. ∀g, M(x, g) ∈ {⊥} ∪ SOL(X), i. e., every guess leads M to output either a solution or “don’t know.”
Note that the time bound in item 1 does not depend on g, which is useful for our purpose.
We can now state the main technical result of this section. We prove it in Section 3.1, and then use it
in Section 3.2 to prove Theorem 1.3.
Theorem 3.2. The nondeterministic complexity of constructing a cut-equivalent tree for an input graph
with unit edge-capacities is O(m),
e where m is the number edges in the graph.
This algorithm employs the Gomory–Hu algorithm in a very specific manner, where the vertices
chosen at each iteration are “centroids” (see below). The same choice was previously used by Anari
and Vazirani [10] in the context of parallel algorithms (for planar edge-capacitated graphs), to achieve a
logarithmic recursion depth, which is key for parallel time. However, since our goal is different (we want
near-linear total time) we have to worry about additional issues, besides the depth of the recursion. Many
auxiliary graphs must be handled throughout the execution of the algorithm, and for each one we need
to verify multiple minimum cuts. This is done by guessing cuts and flows, and the main challenge is to
argue that the total size of all these objects (the auxiliary graphs, and the cuts and flows within them) is
only O(m).
e Towards overcoming this challenge, we show a basic structural result about cut-equivalent
trees (see Claim 3.9 below) which may have other applications. Prior to our work, it seemed unlikely that
the Gomory–Hu approach could come close to near-linear time, even if Max-Flow could be computed in
linear time, since a Max-Flow computation is executed many times in many auxiliary graphs. However,
our analysis shows that the total size of all these auxiliary graphs can be near-linear (if the right vertices
are chosen at each iteration), giving hope that this approach may still achieve the desired upper bound.
3.1 The nondeterministic algorithm
We now prove Theorem 3.2. Let G = (V, E) be the input graph, and let n = |V | and m = |E|.
Overview. At a high level, the nondeterministic algorithm first guesses nondeterministically a cut-
equivalent tree T ∗ , and then verifies it by a (nondeterministic) process that resembles an execution of the
Gomory–Hu algorithm that produces T ∗ . Similarly to the actual Gomory–Hu algorithm, our verification
process is iterative and maintains a tree T of super-nodes, which means, as described in Section 2, that
every tree node i is associated with Vi ⊆ V , and these super-nodes form a partition V = V1 t · · · tVl . This
tree T is initialized to have a single super-node corresponding to V and then modified at each iteration,
hence we shall call it the intermediate tree. If all guesses work well, then eventually every super-node is a
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 10
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
singleton and the tree T corresponds to T ∗ . Otherwise (some step in the verification fails), the algorithm
outputs ⊥.
In a true Gomory–Hu execution, every iteration partitions some super-node into exactly two super-
nodes connected by an edge (say Vi = S t T ). In contrast, every iteration of our verification process
partitions some super-node into multiple super-nodes that form a star topology, whose center is a singleton
(say Vi = {w} tVi,1 t · · · tVi,d , where super-node {w} has edges to all super-nodes Vi,1 , . . . ,Vi,d ). We call
this an expansion step (see Figure 2), and the node in the center of the star (i. e., w) the expanded node.
These expansion steps will be determined from the guess T ∗ . For example, in the extreme case that T ∗
itself is a star, our verification process will take only one expansion step instead of |V | − 1 Gomory–Hu
steps.
𝑉 T ∗𝑐𝑗
𝑈1
𝑈5
𝑐𝑗 𝑈2
𝑐𝑗
𝑈4
𝑈3
Figure 2: An illustration of the verification of a guessed tree T ∗ . Left: the intermediate tree T right before
an expansion step of the node c j in the super-node V (Tc∗j ). Middle: after the expansion step (of c j , in the
dashed circle) where U1 , ...,U4 are c j ’s neighbors in T ( j+1) such that 4i=1 Ui ∪ {c j } = V (Tc∗j ). Right: the
S
guessed cut-equivalent tree T ∗ .
To prove that our algorithm is correct, we will show that every expansion step corresponds to a valid
sequence of steps in the Gomory–Hu algorithm. As the latter relies on minimum-cut computations in
some auxiliary graph G0 , also our verification will need minimum-cut computations, which can be easily
performed in nondeterministic linear time. However, this will not achieve overall running time O(m), e
because in some scenarios (e. g., in the above example where T is a star), most of the |V | − 1 minimum-
∗
cut computations are performed on an auxiliary graph G0 of size that is comparable to G, i. e., Ω(m). We
overcome this obstacle using two ideas. First, we compute simultaneously all the minimum-cuts of the
same expansion step in nondeterministic time that is linear in the size of G0 . Second, we design a specific
sequence of expansion steps such that the total size of all auxiliary graphs G0 is O(m).
e
Detailed algorithm. The algorithm first guesses nondeterministically an edge-capacitated tree T ∗ , and
then verifies, as explained below, that it is a cut-equivalent tree. Here, verification means that upon the
failure of any step, e. g., verifying some equality (say between the cut and flow values), the algorithm
terminates with output ⊥. (By the same reasoning, we may assume that all guesses are proper, e. g., a
guessed tree is indeed a tree.) The verification process starts by picking a sequence of nodes c0 , c1 , c2 , . . .
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 11
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
using the guess T ∗ , as follows. Recall that a centroid of a tree is a node whose removal disconnects
the tree into connected components (subtrees), each containing at most half the nodes in the tree. It is
well-known that in every tree, a centroid exists and can be found in linear time. In a recursive centroid
decomposition of a tree, one finds a centroid of the given tree, removes it and then repeats the process
recursively in every connected component, until all remaining components are singletons (have size one).
Our verification process computes this decomposition for the guess T ∗ , which takes time O(n log n). For
each recursion depth i ≥ 0 (where clearly i ≤ log n), denote the set of centroids computed at depth i by
Di ⊂ V . For example, D0 contains exactly one centroid, of the entire T ∗ . Now let c0 , c1 , c2 , . . . be the
centroids in this decomposition in order of increasing depth, i. e., starting with the one centroid c0 ∈ D0 ,
followed by the centroids from D1 (ordered arbitrarily), and so forth. Let Tc∗j be the subtree of T ∗ in
which the centroid c j was computed; for example Tc∗0 = T ∗ .
Observation 3.3. For every two centroids from the same depth, c j 6= c j0 ∈ Di , the corresponding subtrees
Tc∗j and Tc∗j0 are node disjoint.
The verification process now initializes a tree T, called the intermediate tree, to consist of a single
super-node associated with V , and then performs on it expansion steps for nodes c0 , c1 , c2 , . . . (in this
order) as explained below.
We now explain how to perform an expansion step for node c j . Recall that c j is a centroid of
the subtree Tc∗j , therefore it defines a partition V (Tc∗j ) = {c j } t U1 t · · · tUd , where U1 , . . . ,Ud are the
connected components after removing c j . Notice that d = degTc∗ (c j ) ≤ degT∗ (c j ), and that each Uk ,
j
k ∈ [d], contains exactly one node uk ∈ Uk that is a neighbor of c j in Tc∗j . The expansion step replaces
the super-node V (Tc∗j ) in T with d + 1 super-nodes {c j },U1 , . . . ,Ud . (We slightly abuse notation and use
a subset of nodes like V (Tc∗j ) also to refer to the super-node in T associated with this subset.) These
d + 1 new super-nodes are connected by a star topology, where the singleton {c j } at the center and each
newly-added edge ({c j },Uk ) is set to the same capacity as the edge (c j , uk ) in the guess T ∗ . In addition,
every edge that was incident to super-node V (Tc∗j ), say (V (Tc∗j ),W ), is modified to an edge (U,W ), where
U is one of the new super-nodes {c j },U1 , . . . ,Ud , chosen according to the edge in T ∗ that was used to
set a capacity for (V (Tc∗j ),W ). (We will explain how the algorithm verifies the correctness of these edge
weights shortly.)
It is easy to verify that the modifications to T (due to expansion steps) maintain the following
property: Every super-node U in T induces a subtree of T ∗ , i. e., the induced subgraph T ∗ [U] is connected.
Moreover, eventually every super-node will be a singleton, and the intermediate tree will exactly match
the guess T ∗ . When we need disambiguation, we may use T ( j) to denote the tree’s state before the
expansion step for c j . For example, T (0) is the initial tree with a single super-node V .
Informally, the verification algorithm still has to check that the capacities of the newly-added tree
edges correctly represent minimum-cut values. To this end, the algorithm now constructs an auxiliary
graph G0j just as in the Gomory–Hu algorithm (see Section 2). Specifically, G0j is constructed by taking
G, and then for each connected component of T ( j) \ {V (Tc∗j )} (i. e., after removing super-node V (Tc∗j )
from T ( j) ), merging the nodes in (all the super-nodes in) this component into a single node. Our analysis
shows (in Claim 3.6) that for all s,t ∈ V (Tc∗j ), every minimum st-cut in the auxiliary graph G0j is also
a minimum st-cut in G. In addition, all the auxiliary graphs of a single depth q can be constructed in
near-linear time (Lemma 3.10).
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 12
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
Observe that each neighbor uk of c j in Tc∗j defines a (c j , uk )-cut in the auxiliary graph G0j , given by
the two connected components of T ∗ \ {(c j , uk )}. The algorithm evaluates for each uk the capacity of this
cut in G0j , and verifies that it is equal to the capacity of the newly-added edge ({c j },Uk ) (set to be the
same as of edge (c j , uk ) in T ∗ ). In fact, all these cuts evaluations are performed not sequentially but rather
simultaneously for all k ∈ [d], as follows. The key observation is that if we denote each aforementioned
(c j , uk )-cut by (V (G0j ) \Ck0 ,Ck0 ), where uk ∈ Ck0 , then {c j },C10 , . . . ,Cd0 are disjoint subsets of V (G0j ). One
can clearly evaluate the capacity of all these d cuts in a single pass over the edges of G0j , and since
each edge contributes to at most two cuts (by the disjointness), this entire pass takes only linear time
O(|E(G0j )|).
Next, to verify that each (c j , uk )-cut exhibited above, namely, each (V (G0j ) \ Ck0 ,Ck0 ), is actually a
minimum (c j , uk )-cut in G0j , the algorithm finds a flow whose value is equal to the cut capacity. In order
to perform this task simultaneously for all k ∈ [d], our verification algorithm employs a known result
about disjoint trees, as a witness for maximum-flow values in a graph with unit edge-capacities (strictly
speaking, this witness provides lower bounds on maximum-flow values). In the following theorem, a
directed tree rooted at r is a directed graph arising from an undirected tree all of whose edges are then
directed away from r. This is equivalent to an arborescence (having exactly one path from r to every
node), however we will not require that it spans all the graph nodes. In the following, Max-FlowG (s,t) is
the maximum st-flow value in a graph G.
Lemma 3.4. Given an undirected multigraph H = (VH , EH ), a root node r ∈ VH , and a function λ : VH →
[|EH |], it is possible to nondeterministically verify in time O(|E
e H |) that
∀v ∈ VH \ {r}, Max-FlowH (r, v) ≥ λ (v). (3.1)
Here, nondeterministic verification means that if (3.1) holds then there exists a guess that leads to output
“yes”; and if (3.1) does not hold then every guess leads to output “no.”
Proof. We use the following theorem known from [12, Theorem 2.7], in its variation from [19] as the
Tree Packing Theorem.
Theorem 3.5. Let He be an Eulerian directed graph, and re be a node in He . Then there exist
maxv6=re {Max-FlowHe (re , v)} edge-disjoint directed trees rooted at re , such that each node v ∈ He appears
in exactly Max-FlowHe (re , v) trees.
Given the undirected multigraph H, first subdivide each edge into two edges with a new node in
between them, then orient each edge in both directions7 to obtain an Eulerian directed graph He . Observe
that the minimum-cut values between pairs of original nodes in He are the same as in H. Now find all
maximum-flow lower-bound values from r in He by guessing |VH | edge-disjoint trees and then counting
occurrences of each node in those trees. By Theorem 3.5, these counts correspond to maximum-flow
lower-bound values from r. And so if the guessed trees support the values given by λ , then answer “yes,”
and otherwise answer “no.” Note that the conversion to directed Eulerian graph multiplied the amount of
edges by 2, and so the running time is still near linear.
7 The subdivision and orientation are used to transform the undirected multigraph to a directed graph.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 13
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
The verification algorithm then applies Lemma 3.4 to G0j with c j as the root, and verifies in time
O(|E(G 0 )|) that the maximum-flow from c to each u is at least the capacity of the (c , u )-cut exhibited
j k j k
e
j
above (in turn verified to be equal to the capacity of edge (c j , uk ) in T ∗ ).
Correctness. We begin by claiming that if the guessed tree T ∗ is a correct cut-equivalent tree of G, then
our algorithm outputs T ∗ ; we discuss the complement case afterwards. Since T ∗ is a cut-equivalent tree,
every verification step of an expansion will not fail and so the algorithm will not terminate prematurely,
and output T ∗ , as required.
Next, we show that if T ∗ is not a cut equivalent tree, then our algorithm will not succeed. This is
proved mainly by the claim below, that an intermediate tree attained by expansion steps can be attained
also by a sequence of Gomory–Hu steps.
Claim 3.6. If there is a sequence of Gomory–Hu steps simulating expansions attaining T ( j) , and another
expansion step is being done to attain T ( j+1) , then there is a sequence of Gomory–Hu steps simulating
this last step too.
Proof. Assume there is a truncated execution of the Gomory–Hu algorithm that produces T ( j) . We
describe a sequence of Gomory–Hu algorithm’s steps starting with T ( j) that produces T ( j+1) . Recall that
U1 , ...,Ud are {c j }’s neighbors in T ( j+1) such that di=1 Ui ∪ {c j } = V (Tc∗j ), and u1 , ..., ud are the nodes
S
by which the capacities of the edges ({c j },Uk ), k ∈ [d], were chosen.
The Gomory–Hu steps are as follows, where we denote by T the intermediate tree along the execution.
Starting with T = T ( j) , for k = 1, ..., d, the Gomory–Hu execution picks the pair c j , uk from the super-node
containing it in T as the pair s,t in the Gomory–Hu algorithm description (see the description in Section 2),
and the given minimum-cut value between them is asserted. Then, for the partitioning of this super-node
in T, the execution picks the minimum-cut between c j , uk as in T ∗ (which is a minimum cut also in
the corresponding auxiliary graph) and modifies the intermediate tree accordingly. Note that the last
expansion step was assumed to be successful (i. e., verified correctly), thus all the cuts chosen for the
partitioning are minimum-cuts.
Now, assume for the contrary that T ∗ is not a cut-equivalent tree of G and our algorithm still produces
it. As a consequence of Claim 3.6, there is a sequence of Gomory–Hu steps attaining T ∗ , contradicting
the proof of correctness of the Gomory–Hu algorithm (which cannot produce T ∗ ). Thus, it is impossible
that our algorithm finishes and produces T ∗ , and so in one of the minimum-cut verifications after an
expansion step, the cut witness inspired from T ∗ would not be correct, or there would not be a set of
directed trees to testify that the corresponding cuts are minimal. This completes the proof of correctness.
Running time. Observe that the running time of a single expansion step, i. e., verifying its corresponding
minimum cuts by evaluating cuts and flows, is near-linear in the size of the auxiliary graph. Thus, we
only have to show that the total size of all the auxiliary graphs (over all the expansions) is near-linear
in m. We prove in Lemma 3.7 below an O(m) bound for a single depth q, and since the depth of the
decomposition is O(log n), we immediately conclude in Corollary 3.8 that the total size of all auxiliary
graphs over all depths is O(m).
e
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 14
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
Lemma 3.7. Let Dq = {c j1 , . . . , c j2 } contain the centroids at depth q. Then the total size of G0j1 , . . . , G0j2
is at most O(m).
Corollary 3.8. The total size of all auxiliary graphs (over all depths) is O(m).
e
Proof of Lemma 3.7. Let us count for each edge uv ∈ E(G) in how many auxiliary graphs of depth q it
appears. This quantity turns out to be at most 2 + (distT (u, v) − 1), where distT (u, v) is the hop-distance,
i. e., the minimum number of edges (ignoring weights or capacities) in a path between u and v in the
tree T. The summand 2 comes from edges uv such that either u or v belong to V (Tc j ) for some auxiliary
graph G0j . Clearly, every such edge is in at most two auxiliary graphs at depth q, because there is at most
one index j0 ∈ Dq where u ∈ V (Tc j0 ) and at most one index j00 ∈ Dq where v ∈ V (Tc j00 ). The summand
distT (u, v) − 1 bounds the other appearances of edge uv, i. e., when neither u nor v belongs to some
V (Tc j ), and is proved in the claim below. While our graph has unit capacities, the claim holds for general
capacities.
Claim 3.9. For every cut-equivalent tree T of a graph G with edge capacities cG : E → R+ ,
∑ cG (u, v) · distT (u, v) ≤ 2 ∑ cG (u, v).
uv∈E(G) uv∈E(G)
Proof. We first show that ∑uv∈EG cG (u, v) · distT (u, v) = ∑e∈ET cT (e), where cT (·) denotes edge capacity
in T. Recalling that T is a cut-equivalent tree, each cT (e) is the value of a certain cut in G, hence we
can evaluate the right-hand side differently, by summing over the graph edges uv ∈ E(G) and counting
for each edge in how many such cuts it appears. Moreover, the count for each graph edge uv ∈ E(G) is
exactly distT (u, v) contributions of cG (u, v), giving altogether the left-hand side.
Second, we show that ∑uv∈E(T) cT (u, v) ≤ 2 ∑uv∈E(G) cG (u, v) (see also Lemma 4 in [13]). To see this,
observe that cT (u, v) ≤ min{degcG (u), degcG (v)} where degcG (u) is the total capacity of edges incident to
u. Now fix a root vertex in T, and bound each tree edge by cT (u, v) ≤ degcG (v), where v is the child of
u (i. e., farther from the root) in T. Summing this bound over all the tree edges and observing that the
corresponding vertices v are all distinct proves the desired inequality, and the claim follows.
To complete the proof of Lemma 3.7, recall that by Observation 3.3 the super-nodes V (Tc j1 ), . . . ,
V (Tc j2 ) of the same depth q are pairwise disjoint. Thus, an edge uv appears in at most distT∗ (u, v) − 1
auxiliary graphs of depth q, which totals to O(m) for all the edges in this depth according to the unit
edge-capacity special case of the above Claim 3.9. This concludes Lemma 3.7.
Next, we bound the time it takes to construct all the auxiliary graphs.
Lemma 3.10. The total time it takes to construct the auxiliary graphs for all the expansions in the
centroid decomposition is O(m).
e
Proof. Let c j be a node that is expanded at some depth q ≥ 1, and let c j,1 , . . . , c j,d be the expanded nodes
in U1 , . . . ,Ud , respectively at depth q + 1 (or just ⊥ for singletons).
Note that G0j,1 , . . . , G0j,d (whichever exist) can all be constructed in total time that is linear in the size
of G0j .
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 15
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
Thus, the total time it takes to construct the auxiliary graphs at a single depth q is linear in the size of
the auxiliary graphs in the parent depth. Since the auxiliary graph at depth 0 (i. e., the entire graph) can
trivially be constructed in O(m) time and is linear in the input size, it follows by Corollary 3.8 that the
total construction time of the auxiliary graphs for all depths takes at most O(m)e time.
3.2 Reduction from a decision problem to a total search problem
Let us start with the formal statement of NSETH.
Hypothesis 3.11 (Nondeterministic Strong Exponential-Time Hypothesis (NSETH)). For every ε > 0
there exists k = k(ε) such that k-TAUT (the language of all k-DNF formulas that are tautologies) is not in
NTIME(2n(1−ε) ).
Note that deciding if a k-DNF formula is a tautology is equivalent to deciding if a k-CNF formula is
satisfiable, thus the above hypothesis could be stated also using k-CNF appropriately. Next, we define
(deterministic) fine-grained reductions from a decision problem to a total search problem. Note that these
are Turing reductions.
Definition 3.12 (Fine-Grained Reduction from a Decision Problem to a total search problem). Let L be a
language and P be a total search problem, and let TL (·) and TP (·) be time bounds. We say that (L, TL )
admits a fine-grained reduction to (P, TP ) if for all ε > 0 there is a γ > 0 and a deterministic Turing
machine M P (with an access to an oracle that generates a solution to every instance of P) such that:
1. M P decides L correctly on all inputs when given a correct oracle for P.
e P , x) denote the set of oracle queries made by M P on input x of length n. Then the query
2. Let Q(M
lengths obey the bound
∀x, THALT (M P , |x|) + ∑ (TP (|q|))1−ε ≤ (TL (n))1−γ ,
q∈Q(M,x)
e
where THALT (M P , |x|) is the maximal time M P runs on inputs of size |x|.
We are now ready to prove the non-reducibility result under NSETH for total search problems with
small nondeterministic complexity. The proof arguments are similar to those of Carmosino et al. [16].
Theorem 3.13. Suppose P is a total search problem with nondeterministic time complexity T (m). If for
some δ > 0 there is a deterministic fine-grained reduction from k-SAT with time-bound 2n to P with time
bound T (m)1+δ , i. e., from (k-SAT, 2n ) to (P, T (m)1+δ ), then NSETH is false.
Proof. We will use the assumption of the theorem to describe a nondeterministic algorithm for k-TAUT
that refutes NSETH. Let φ be an instance of k-TAUT, and note that φ ∈ k-TAUT iff ¬φ ∈ / k-SAT. Our
nondeterministic algorithm A first computes the CNF formula ¬φ , then simulates the assumed reduction
M1 from k-SAT to P on ¬φ , and eventually outputs the negation of the simulation’s answer, or Reject if
the simulation returns ⊥.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 16
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
Let M2 be the Turing Machine showing that P has nondeterministic time complexity T (m). Whenever
the reduction M1 produces a query to P, our algorithm A executes M2 on this query with some guess
string g. Let gi be the guess string used for the ith query to P made by M1 . If any of the executions of M2
throughout the simulation outputs ⊥, then A stops and outputs Reject. Otherwise (all executions output
valid answers), the simulation continues until M1 terminates. At this point, the output of M1 must be
correct, and our algorithm A outputs the opposite answer.
Let us argue about the correctness of our algorithm. First, it only outputs Accept if the guesses and all
answers to the P-queries were correct and then M1 rejected, meaning that ¬φ ∈ / k-SAT i. e., φ ∈ k-TAUT.
Second, for every yes-instance φ ∈ k-TAUT there is at least one sequence of guesses g1 , g2 , . . . that makes
A output Accept, due to the correctness of the reduction M1 and the fact that M2 nondeterministically
computes P correctly. Finally, the running time of A can be upper bounded by
THALT (M1 ) + ∑ T (|q|) ≤ THALT (M1 ) + ∑ T (|q|)(1+δ )(1−ε) ≤ (2n )1−γ
e 1 ,x)
q∈Q(M e 1 ,x)
q∈Q(M
for 0 < ε < δ where the last inequality is due to the reduction from k-SAT to P, THALT (M1 ) is the time
e 1 , x) is the queries made by M1 to the P-oracle on an input x, and the last
of operations done by M1 , Q(M
inequality follows for some γ(ε) > 0 because M1 is a correct fine-grained reduction. Thus, A refutes
NSETH.
Since the construction of a cut-equivalent tree is a total search problem, and by Theorem 1.2 its
nondeterministic complexity is O(m),
e applying Theorem 3.13 implies that any deterministic reduction
from SETH to the construction of a cut-equivalent tree that implies a lower bound of Ω(m1+δ ), for some
δ > 0, would refute NSETH, concluding Theorem 1.3.
4 Conditional lower bound for All-Pairs Max-Flow
In this section we prove a conditional lower bound for All-Pairs Max-Flow in undirected graphs with node
capacities. Our construction is inspired by the one in [33], which was designed for directed graphs with
edge capacities, but we adapt it to undirected graphs with node capacities using our new trick described
in the introduction. In fact, readers familiar with the reduction in [33] may notice that we had to tweak it
a little, making it simpler in certain ways but more complicated in others. This was necessary in order to
apply our new trick to it.
The starting point for our reduction is the 3OV problem.
Definition 4.1 (3OV). Given three sets U1 ,U2 ,U3 ⊆ {0, 1}d containing n binary vectors each, over
dimension d, decide if there is a triple (α, β , γ) of vectors in U1 ×U2 ×U3 , whose dot product is 0. That
is, a triple for which for all i ∈ [d] at least one of α[i], β [i], γ[i] is equal to 0.
An adaptation of the reduction by Williams [45] shows that 3OV cannot be solved in O(n3−ε ) time
for any ε > 0 and d = ω(log n), unless SETH is false (see [1]). For us, it suffices to assume the milder
conjecture that 3OV cannot be solved in O(n3−ε ) time when d = nδ , for all ε, δ > 0. Refuting this
conjecture would have important implications beyond refuting SETH [23, 2], e. g., it would refute the
Weighted Clique Conjecture.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 17
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
The high-level structure of the reduction is the following. Create three layers of nodes that correspond
to the three sets of vectors, with additional two layers in between them that correspond to the coordinates.
These additional layers help keep the number of edges small by avoiding direct edges between pairs of
vectors. Among other things, we utilize the trick described in the introduction and set the capacity of the
nodes in the leftmost and rightmost sides to be 1, while making the other capacities much larger. This
way a flow would not gain too much from crisscrossing through these nodes. Formally, we prove the
following.
Lemma 4.2. 3OV over vector sets of size n and dimension d can be reduced to All-Pairs Max-Flow in
undirected graphs with Θ(n · d) nodes, Θ(n · d) edges, and node capacities in [2n2 d].
Since, as explained earlier, the 3OV conjecture is a consequence of SETH, Theorem 1.1 immediately
follows from Lemma 4.2, which is proved below.
Proof of Lemma 4.2. Given a 3OV instance F we construct a graph G with maximum flow size between
some pair (among a certain set of pairs) bounded by a certain amount if and only if F is a yes instance.
For simplicity, we first provide a construction that has some of the edges directed (only where we will
specifically mention that), and then we show how to avoid these directions. In addition, some of the edges
will be capacitated as well. However, the amount of such edges is small enough so that subdividing them
with appropriate capacitated nodes will work too without a significant change to the size of the graph
constructed.
An intermediate construction with few directed edges. To simplify the exposition, we start with
a construction of a graph G0 in which most of the edges are undirected, but some are still directed
(see Figure 3).
Our final graph G will be very similar to G0 . It will have the same nodes and edges except that all
edges will be undirected and the capacities on the nodes will be a little different.
We construct the graph G0 on N nodes V1 ∪V2 ∪V3 ∪ A ∪ B ∪ {vB }. The layer V1 contains a node α of
capacity 1 for every vector α ∈ U1 . V2 contains d + 1 nodes for every vector β ∈ U2 : d nodes of capacity
1 denoted by βi for every i ∈ [d], plus a node denoted by β 0 of capacity d − 1. V3 contains a node γ of
capacity 1 for every vector γ in U3 . The intermediate layer A contains 2d nodes: two nodes Ci0 and Ci1
of capacity n for every coordinate i ∈ [d]. The other intermediate layer B contains a node Ci of capacity
n for every coordinate i ∈ [d]. Finally, the auxiliary node vB has capacity n(d − 1). With a slight abuse
of notation, we will use the following symbols in the following ways: α will be either a node in V1 or a
vector in U1 ; β will be a vector in U2 ; γ will be either a node in V3 or a vector in U3 ; and Ci will be either
a node in B or a coordinate in [d]. The usage will be clear from context.
The edges of the network will be defined as follows. First, we describe the edges that depend on the
given 3OV instance.
• For every α and i ∈ [d], we add a directed edge from α to Ci0 if α[i] = 0, and a directed edge from
α to Ci1 if α[i] = 1.
• For every β , we add an (undirected) edge from βi to Ci if β [i] = 1.
• For every γ and i ∈ [d], we add an (undirected) edge from Ci to γ if γ[i] = 1.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 18
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
d−1 n(d − 1)
0
1 β vB
β1
1
n
β2
C10
n
n
C11 1 C1
β3
n
1 C20 1
n
α γ
n C21 C2
d−1
n 1 β̃ 0
1 C30 β̃1 1
n
α̃ n
C31 C3
γ̃
1
β̃2
1
β̃3
Figure 3: An illustration of part of the reduction. Here, U1 , U2 , and U3 have two vectors each; α and α e in
U1 , β and β in U2 , γ and γe in U3 . Bolder nodes correspond to nodes of higher capacity, and dashed edges
e
are conditional on the input instance. For simplicity, we omit the edges not relevant to α and γe, and also
the edges from nodes in {Ci0 }i∈[3] to nodes in {β 0 , βe0 }. In this illustration, α = 110, β = 101, βe = 001,
and γe = 101. Note that the triple α, βe, and γe has an inner product 0, and indeed the maximum flow from
α to γe is 2 · 3 − 1 = 5.
Moreover, there will be some (undirected) edges that are independent of the vectors. For every β , we
have an edge of capacity 1 from Ci0 to β 0 , and an edge of capacity 1 from Ci1 to βi . Also, for every β , we
have an edge from βi to β 0 , and an edge from β 0 to vB . Finally, for every γ, we have an edge from vB to
γ ∈ V3 . (Unless specified otherwise, these edges have no capacity constraints.)
The graph built has N = n + 2d + n · d + n + 1 + d + n = Θ(nd) nodes, at most O(nd) edges, all of its
capacities are in [N], and its construction time is O(nd).
The following two claims prove the correctness of this intermediate reduction.
Claim 4.3. If every triple of vectors in (U1 ,U2 ,U3 ) has inner product at least 1, then for all pairs
α ∈ V1 , γ ∈ V3 the maximum-flow in G0 is at least n · d.
Proof. Assume that every triple of vectors in (U1 ,U2 ,U3 ) has inner product at least 1, and fix some α
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 19
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
and γ. We will explain how to send n · d units of flow from α to γ in G0 . By the assumption, for every β
there exist an i ∈ [d] such that α[i] = β [i] = γ[i] = 1, and denote this index by iβ . Each iβ induces a path
(α → Ci1β → βiβ → Ciβ → γ) from α to γ, and so we pass a single unit of flow through every one of them,
in what we call the first phase. Note that so far, the flow sums up to n, and we carry on with describing
the second phase of flow through nodes of the form β 0 .
We claim that for every β , an additional amount of (d − 1) units can pass through β 0 , which
would add up to a total flow of n(d − 1) + n = nd, concluding the proof. Indeed, for every β , we
send flow in the following way. For every i ∈ [d] \ iβ , if α[i] = 1 then we send a single unit through
(α → Ci1 → βi → β 0 → vB → γ), and otherwise we send a unit of flow through (α → Ci0 → β 0 → vB → γ).
Since we defined the flow in paths, we only need to show that the capacity constraints are satisfied.
Nodes of the form Ci are only used in the first phase, and the flow through them equals n in total, and so
their flow is within the capacity. The node vB is only used in the second phase and has n(d − 1) units of
flow passing through it, just as its capacity. For every β and i = iβ , we pass in the first phase a single unit
of flow through βi . For every β and i 6= iβ , we transfer in the second phase a unit of flow through βi if
and only if α[i] = 1, thus it is bounded. For every β 0 , we pass in the second phase exactly (d − 1) units of
flow through β 0 , preserving its capacity. For every Cij ∈ N(α), where for a node x we denote by N(x) the
set of nodes adjacent to x, with i ∈ [d] and j ∈ {0, 1}, we pass a total of n units of flow to nodes in V2 ,
one unit on each edge, thus the capacities are preserved, concluding the proof.
Claim 4.4. If there is a triple of vectors (αΦ , βΦ , γΦ ) ∈ (U1 ,U2 ,U3 ) whose inner product is 0, then the
maximum-flow in G0 from αΦ ∈ V1 to γΦ ∈ V3 is at most nd − 1.
Proof. Assume for contradiction that there exists such a flow of value at least nd, and denote it by f . Let
f = {p1 , ..., p| f | } be a description of f as a (multi-)set of paths of single units of flow. By our construction,
the total capacity of all nodes in N(αΦ ) sums up to nd exactly. Therefore, f must have all of the nodes in
N(αΦ ) saturated.
Consider a node Cij ∈ N(αΦ ) for some i ∈ [d] and j ∈ {0, 1}. Note that Cij is saturated in f while its
capacity is n and it has exactly n edges adjacent to it (excluding the edges incoming from V1 ) of capacity
1 each. Therefore, we get that every node in N(Cij ) \V1 must receive a single unit of flow from Cij in f .
Hence, every β -cloud, which we define as all the nodes that are associated with a β , must have exactly d
flow paths in f for which it is the first β -cloud that they pass through. We call this a first passing of a
path through a β -cloud. In particular, for every β and for every i ∈ [d] such that αΦ [i] = 1 there must be
a path pβ ,i in f whose prefix is (αΦ ,Ci1 , βi , ...).
Our main claim is that the βΦ -cloud can only have up to d − 1 flow paths that are first passing through
it. Clearly, if there are more, then at least one of them does not pass through βΦ 0 (whose capacity is only
d − 1), so name this path p0 . We will argue that this path must be in conflict with one of the pβ ,i paths
described above.
For some i ∈ [d] the prefix of p0 must be (αΦ ,Ci1 , βΦi ,Ci , ...), since this is the only way it can avoid
the node βΦ 0 . This can only happen for an i ∈ [d] for which α[i] = β [i] = 1, or else those edges will not
exist in G. But since (αΦ , βΦ , γΦ ) is a triple whose inner product is 0, it must be that γΦ [i] = 0 and so the
edge {Ci , γ} is not in the graph. Hence, after Ci this path can only go to a node βei for some βe, and the
(longer) prefix of p0 must be (αΦ ,Ci1 , βi ,Ci , βei , ...). Note that this is the same index i, and we know that
αΦ [i] = 1. Therefore, by the above, we know that there is another path pβe,i in f that has βei as the third
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 20
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
node on the path. (That is, there is already a path that is first-passing through βei .) This is a contradiction
to the fact that the capacity of βei is 1.
The final construction. The main issue with avoiding the directions on the edges between nodes in V1
and A, is that additional α’s might participate in the flow as well, potentially allowing one additional unit
of flow to pass through. As described in the introduction, the solution is to multiply the capacities of all
nodes that are not in V1 ∪V3 by 2n. This is how we get our final graph G from G0 . In the following we
show how this modification concludes the proof of Lemma 4.2.
Claim 4.5. If every triple of vectors in (U1 ,U2 ,U3 ) has inner product at least 1, then for all pairs
α ∈ V1 , γ ∈ V3 the maximum-flow in G is at least 2n2 d.
Proof. Since the flow that was defined in Claim 4.3 does not touch nodes in V1 ∪V3 , considering the same
flow in G but multiplied by 2n, we get a new flow that is of size nd · (2n), concluding the proof.
Claim 4.6. If there is a triple of vectors (αΦ , βΦ , γΦ ) ∈ (U1 ,U2 ,U3 ) whose inner product is 0, then the
maximum-flow in G from αΦ ∈ V1 to γΦ ∈ V3 is at most 2n2 d − 1.
Proof. Let f be the maximum flow from αΦ to γΦ in G. The paths in f can be divided into two kinds:
paths that pass through nodes in (V1 ∪ V3 ) \ {αΦ , γΦ }, and paths that do not. The total contribution
of paths of the first kind can be upper bounded by the size of (V1 ∪ V3 ) \ {αΦ , γΦ }, which is 2n − 2,
since the capacity of all nodes in this set is 1. On the other hand, paths from the second kind must
obey the directions of the directed edges in G0 and can therefore be used in G0 , except that in G their
multiplicity (the amount of flow we push through them) can be larger by a factor of 2n. Therefore, we
can upper bound the total contribution of paths of the second kind by 2n times the maximum flow in
G0 , which is (nd − 1)(2n). Thus, the overall flow is at most (nd − 1)(2n) + 2n − 2 = 2n2 d − 2, which
proves Claim 4.6.
Since we showed a gap of at least one unit of flow between the yes and the no instances, the proof of
Lemma 4.2 is concluded.
5 Open problems
Many gaps and open questions around the complexity of maximum flow remain after this work. We
highlight a few for which our intuitions may have changed following our discoveries.
• Can we break the O(mn) barrier also when the graphs have arbitrary (polynomial) capacities? Our
result gives hope that this may be possible.
• Can we reduce the directed case to the undirected, node-capacitated case? Because of our lower
bound, it is likely that both of these cases will end up having the same time complexity, and so
such a reduction may be possible.
Note added in proof. Ongoing work by the current authors indeed provides such a reduction but
only for the sparse case.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 21
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
• Can we generalize the nondeterministic algorithm to arbitrary edge capacities? Notice that one
obstacle for achieving that goal is finding lower bounds witnesses for flows from a certain source
to other nodes.
• Can we prove any conditional lower bound for All-Pairs Max-Flow in undirected graphs with edge
capacities? This is obviously the most important and intriguing open question in this context.
Our new deterministic and nondeterministic upper bounds make this task more challenging than
previously thought.
6 Acknowledgments
We would like to thank Arturs Backurs for asking about the nondeterministic complexity of the problems,
Marvin Kunnemann for pointing out the connection to certifying algorithms, and Richard Peng for helpful
comments on the different known upper bounds for Max-Flow.
References
[1] A MIR A BBOUD , A RTURS BACKURS , AND V IRGINIA VASSILEVSKA W ILLIAMS: Tight hardness
results for LCS and other sequence similarity measures. In Proc. 56th FOCS, pp. 59–78. IEEE
Comp. Soc., 2015. [doi:10.1109/FOCS.2015.14] 17
[2] A MIR A BBOUD , K ARL B RINGMANN , H OLGER D ELL , AND J ESPER N EDERLOF: More con-
sequences of falsifying SETH and the orthogonal vectors conjecture. In Proc. 50th STOC, pp.
253–266. ACM Press, 2018. [doi:10.1145/3188745.3188938] 17
[3] A MIR A BBOUD , L OUKAS G EORGIADIS , G IUSEPPE F. I TALIANO , ROBERT K RAUTHGAMER ,
N IKOS PAROTSIDIS , O HAD T RABELSI , P RZEMYSŁAW U ZNA ŃSKI , AND DANIEL W OLLEB -
G RAF: Faster algorithms for all-pairs bounded min-cuts. In Proc. 46th Internat. Colloq. on
Automata, Languages, and Programming (ICALP’19), volume 132, pp. 7:1–7:15. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ICALP.2019.7] 3
[4] A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI: New algorithms and lower
bounds for all-pairs max-flow in undirected graphs. In Proc. 31st Ann. ACM–SIAM Symp. on
Discrete Algorithms (SODA’20), pp. 48–61. SIAM, 2020. [doi:10.1137/1.9781611975994.4,
arXiv:1901.01412] 1
[5] A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI: APMF < APSP? Gomory–
Hu tree for unweighted graphs in almost-quadratic time, 2021. Accepted to FOCS 2021.
[arXiv:2106.02981] 5
[6] A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI: Subcubic algorithms for
Gomory–Hu tree in unweighted graphs. In Proc. 53rd STOC, pp. 1725–1737. ACM Press, 2021.
[doi:10.1145/3406325.3451073] 5
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 22
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
[7] A MIR A BBOUD AND V IRGINIA VASSILEVSKA W ILLIAMS: Popular conjectures imply strong
lower bounds for dynamic problems. In Proc. 55th FOCS, pp. 434–443. IEEE Comp. Soc., 2014.
[doi:10.1109/FOCS.2014.53] 4
[8] A MIR A BBOUD , V IRGINIA VASSILEVSKA W ILLIAMS , AND H UACHENG Y U: Matching triangles
and basing hardness on an extremely popular conjecture. SIAM J. Comput., 47(3):1098–1122, 2018.
Preliminary version in STOC’15. [doi:doi:10.1137/15M1050987] 3
[9] E YAD A LKASSAR , S ASCHA B ÖHME , K URT M EHLHORN , AND C HRISTINE R IZKALLAH: A
framework for the verification of certifying computations. J. Autom. Reason., 52(3):241–273, 2014.
Preliminary version in CAV’11. [doi:10.1007/s10817-013-9289-2] 6
[10] N IMA A NARI AND V IJAY V. VAZIRANI: Planar graph perfect matching is in NC. J. ACM,
67(4):21:1–21:34, 2020. Preliminary version in FOCS’18. [doi:10.1145/3397504] 10
[11] S RINIVASA R AO A RIKATI , S HIVA C HAUDHURI , AND C HRISTOS D. Z AROLIAGIS: All-pairs
min-cut in sparse networks. J. Algorithms, 29(1):82–110, 1998. [doi:10.1006/jagm.1998.0961] 3
[12] J ØRGEN BANG -J ENSEN , A NDRÁS F RANK , AND B ILL JACKSON: Preserving and increas-
ing local edge-connectivity in mixed graphs. SIAM J. Discr. Math., 8(2):155–178, 1995.
[doi:10.1137/S0036142993226983] 13
[13] A NAND B HALGAT, R AMESH H ARIHARAN , T ELIKEPALLI K AVITHA , AND D EBMALYA PANI -
GRAHI : An O(mn)
e Gomory–Hu tree construction algorithm for unweighted graphs. In Proc. 39th
STOC, pp. 605–614. ACM Press, 2007. [doi:10.1145/1250790.1250879] 3, 5, 7, 8, 9, 15
[14] G LENCORA B ORRADAILE , DAVID E PPSTEIN , A MIR NAYYERI , AND C HRISTIAN W ULFF -
N ILSEN: All-pairs minimum cuts in near-linear time for surface-embedded graphs. In Proc. 32nd
Internat. Symp. Comput. Geom. (SoCG’16), pp. 22:1–22:16. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik, 2016. [doi:10.4230/LIPIcs.SoCG.2016.22, arXiv:1411.7055] 3
[15] JAN VAN DEN B RAND , Y IN TAT L EE , YANG P. L IU , T HATCHAPHOL S ARANURAK , A ARON
S IDFORD , Z HAO S ONG , AND D I WANG: Minimum cost flows, MDPs, and `1 -regression in
nearly linear time for dense instances. In Proc. 53rd STOC, pp. 859–869. ACM Press, 2021.
[doi:10.1145/3406325.3451108] 5
[16] M ARCO L. C ARMOSINO , J IAWEI G AO , RUSSELL I MPAGLIAZZO , I VAN M IHAJLIN , R AMAMO -
HAN PATURI , AND S TEFAN S CHNEIDER : Nondeterministic extensions of the strong exponential
time hypothesis and consequences for non-reducibility. In Proc. 7th Innovations in Theoret. Comp.
Sci. Conf. (ITCS’16), pp. 261–270. ACM Press, 2016. [doi:10.1145/2840728.2840746] 2, 6, 9, 16
[17] H O Y EE C HEUNG , L AP C HI L AU , AND K AI M AN L EUNG: Graph connectivities, network coding,
and expander graphs. SIAM J. Comput., 42(3):733–751, 2013. [doi:10.1137/110844970] 3
[18] ROBERT T. C HIEN: Synthesis of a communication net. IBM J. Res. Dev., 4(3):311–320, 1960.
[doi:10.1147/rd.43.0311] 2
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 23
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
[19] R ICHARD C OLE AND R AMESH H ARIHARAN: A fast algorithm for computing Steiner edge
connectivity. In Proc. 35th STOC, pp. 167–176. ACM Press, 2003. [doi:10.1145/780542.780568]
3, 13
[20] JACK E DMONDS: Submodular functions, matroids, and certain polyhedra. In Combinatorial
Structures and Their Appl., Proc. Conf. Calgary 1969, pp. 69–87. Gordon and Breach, 1970.
[doi:10.1007/3-540-36478-1_2] 3
[21] L ESTER R. F ORD AND D ELBERT R. F ULKERSON: Maximal flow through a network. Canad. J.
Math., 8(3):399–404, 1956. [doi:10.4153/CJM-1956-045-5] 2
[22] H AROLD N. G ABOW: A matroid approach to finding edge connectivity and packing arbores-
cences. J. Comput. System Sci., 50(2):259–273, 1995. Preliminary version in STOC’91.
[doi:10.1006/jcss.1995.1022] 3
[23] J IAWEI G AO , RUSSELL I MPAGLIAZZO , A NTONINA KOLOKOLOVA , AND R. RYAN W ILLIAMS:
Completeness for first-order properties on sparse structures with algorithmic applications. ACM
Trans. Algorithms, 15(2):1–35, 2019. Preliminary version in SODA’17. [doi:10.1145/3196275] 17
[24] L OUKAS G EORGIADIS , DANIEL G RAF, G IUSEPPE F. I TALIANO , N IKOS PAROTSIDIS , AND
P RZEMYSŁAW U ZNA ŃSKI: All-pairs 2-reachability in O(nω log n) time. In Proc. 44th Internat.
Colloq. on Automata, Languages, and Programming (ICALP’17), volume 80, pp. 74:1–74:14.
Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ICALP.2017.74] 3
[25] A NDREW V. G OLDBERG AND KOSTAS T SIOUTSIOULIKLIS: Cut tree algorithms: an experimental
study. J. Algorithms, 38(1):51–83, 2001. [doi:10.1006/jagm.2000.1136] 3
[26] R ALPH E. G OMORY AND T E C HIANG H U: Multi-terminal network flows. J. SIAM, 9(4):551–570,
1961. [doi:10.1137/0109047] 2, 3, 7
[27] F RIEDA G RANOT AND R EFAEL H ASSIN: Multi-terminal maximum flows in node-capacitated
networks. Discr. Appl. Math., 13(2-3):157–163, 1986. [doi:10.1016/0166-218X(86)90079-X] 3
[28] DAN G USFIELD: Very simple methods for all pairs network flow analysis. SIAM J. Comput.,
19(1):143–155, 1990. [doi:10.1137/0219009] 2
[29] R AMESH H ARIHARAN , T ELIKEPALLI K AVITHA , AND D EBMALYA PANIGRAHI: Efficient algo-
rithms for computing all low s − t edge connectivities and related problems. In Proc. 18th Ann.
ACM–SIAM Symp. on Discrete Algorithms (SODA’07), pp. 127–136. SIAM, 2007. ACM DL. 3, 7,
8
[30] R EFAEL H ASSIN AND A SAF L EVIN: Flow trees for vertex-capacitated networks. Discr. Appl.
Math., 155(4):572–578, 2007. [doi:10.1016/j.dam.2006.08.012] 3
[31] RUSSELL I MPAGLIAZZO AND R AMAMOHAN PATURI: On the complexity of k-SAT. J. Comput.
System Sci., 62(2):367–375, 2001. [doi:10.1006/jcss.2000.1727] 2
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 24
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
[32] F REDERICK J ELINEK: On the maximum number of different entries in the terminal capac-
ity matrix of oriented communication nets. IRE Trans. Circuit Theory, 10(2):307–308, 1963.
[doi:10.1109/TCT.1963.1082149] 3
[33] ROBERT K RAUTHGAMER AND O HAD T RABELSI: Conditional lower bounds for all-pairs max-flow.
ACM Trans. Algorithms, 14(4):42:1–42:15, 2018. [doi:10.1145/3212510] 3, 4, 5, 17
[34] M ARVIN K ÜNNEMANN: On nondeterministic derandomization of Freivalds’ algorithm:
Consequences, avenues and algorithmic progress. In Proc. 26th Eur. Symp. Algo-
rithms (ESA’18), pp. 56:1–56:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
[doi:10.4230/LIPIcs.ESA.2018.56] 6
[35] JAKUB L ACKI , YAHAV N USSBAUM , P IOTR S ANKOWSKI , AND C HRISTIAN W ULFF -N ILSEN:
Single source – all sinks max flows in planar digraphs. In Proc. 53rd FOCS, pp. 599–608. IEEE
Comp. Soc., 2012. [doi:10.1109/FOCS.2012.66] 3
[36] Y IN TAT L EE AND A√ ARON S IDFORD : Path finding methods for linear programming: Solving
linear programs in O( rank) iterations and faster algorithms for maximum flow. In Proc. 55th
e
FOCS, pp. 424–433. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.52] 2
[37] JASON L I , D EBMALYA PANIGRAHI , AND T HATCHAPHOL S ARANURAK: A nearly optimal all-
pairs min-cuts algorithm in simple graphs, 2021. Accepted to FOCS 2021. [arXiv:2106.02233]
5
[38] YANG P. L IU AND A ARON S IDFORD: Faster energy maximization for faster maximum flow. In
Proc. 52nd STOC, pp. 803–814. ACM Press, 2020. [doi:10.1145/3357713.3384247] 2
[39] A LEKSANDER M ADRY: Computing maximum flow with augmenting electrical flows. In Proc. 57th
FOCS, pp. 593–602. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.70] 2
[40] WATARU M AYEDA: Terminal and branch capacity matrices of a communication net. IRE Trans.
Circuit Theory, 7(3):261–269, 1960. [doi:10.1109/TCT.1960.1086673] 2
[41] WATARU M AYEDA: On oriented communication nets. IRE Trans. Circuit Theory, 9(3):261–267,
1962. [doi:10.1109/TCT.1962.1086912] 3
[42] ROSS M. M C C ONNELL , K URT M EHLHORN , S TEFAN N ÄHER , AND PASCAL S CHWEITZER: Cer-
tifying algorithms. Computer Sci. Review, 5(2):119–161, 2011. [doi:10.1016/j.cosrev.2010.09.009]
6
[43] D EBMALYA PANIGRAHI: Gomory–Hu trees. In M ING -YANG K AO, editor, Encyclopedia of
Algorithms, pp. 858–861. Springer, 2016. [doi:10.1007/978-1-4939-2864-4_168] 3, 8
[44] A ARON S IDFORD AND K EVIN T IAN: Coordinate methods for accelerating `∞ regression and
faster approximate maximum flow. In Proc. 59th FOCS, pp. 922–933. IEEE Comp. Soc., 2018.
[doi:10.1109/FOCS.2018.00091] 9
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 25
A MIR A BBOUD , ROBERT K RAUTHGAMER , AND O HAD T RABELSI
[45] R. RYAN W ILLIAMS: A new algorithm for optimal 2-constraint satisfaction and its implications.
Theoret. Comput. Sci., 348(2–3):357–365, 2005. [doi:10.1016/j.tcs.2005.09.023] 17
[46] R. RYAN W ILLIAMS: Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of
batch evaluation. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 2:1–2:17. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.2, arXiv:1601.04743] 6
[47] Z HENYU W U AND R ICHARD L EAHY: An optimal graph theoretic approach to data clustering:
Theory and its application to image segmentation. ACM Trans. Pattern Anal. Machine Intell.,
15(11):1101–1113, 1993. [doi:10.1109/34.244673] 2
[48] T IANYI Z HANG: Faster cut-equivalent trees in simple graphs, 2021. [arXiv:2106.03305] 5
AUTHORS
Amir Abboud
Department of Computer Science and Applied Mathematics
Senior Scientist
The Weizmann Institute of Science
Rehovot, Israel
amir.abboud weizmann ac il
http://weizmann.ac.il/math/AmirAbboud/home
Robert Krauthgamer
Professor
Department of Computer Science and Applied Mathematics
The Weizmann Institute of Science
Rehovot, Israel
robert.krauthgamer weizmann ac il
http://www.wisdom.weizmann.ac.il/~robi/
Ohad Trabelsi
Postdoc
Department of Electrical Engineering and Computer Science
University of Michigan
Ann Arbor, USA
ohadt umich edu
http://sites.google.com/view/ohadtrabelsi/
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 26
N EW A LGORITHMS AND L OWER B OUNDS FOR A LL -PAIRS M AX -F LOW IN U NDIRECTED G RAPHS
ABOUT THE AUTHORS
A MIR A BBOUD received his Ph. D. at Stanford University in 2017 under Virginia Vassilevska
Williams. He was subsequently a Research Staff Member at the theory group in the IBM
Almaden Research Center. Since 2021, he has been a faculty member at the Weizmann
Institute of Science. Amir mainly works in the emerging field of fine-grained complexity
and algorithms, with a special interest in combinatorial problems on graphs and strings.
His favorite sport is soccer, and on August 14, 2020 his favorite team was FC Barcelona.
ROBERT K RAUTHGAMER (called “Robi” by his friends and colleagues) received his Ph. D.
at the Weizmann Institute of Science in 2001 under Uriel Feige. He was subsequently a
postdoc in Berkeley’s theory group, and then a Research Staff Member at the theory group
in the IBM Almaden Research Center. Since 2007, he has been a faculty member at the
Weizmann Institute of Science. Robi’s main research area is the design of algorithms for
problems involving combinatorial optimization, finite metric spaces, high-dimensional
geometry, data analysis, and related areas. His favorite sport since youth has been
swimming. Once he swam across the Sea of Galilee in a 10 km competitive race, and
was the last one to arrive at the finish line.
O HAD T RABELSI received his Ph. D. at the Weizmann Institute of Science under Robert
Krauthgamer. He was subsequently a postdoc in the same group. Since then, he has
been a postdoc at the Department of Electrical Engineering and Computer Science at
the University of Michigan. Ohad’s research focuses on the design of algorithms, and
their conditional lower bounds via fine-grained reductions. In particular, he likes to study
problems of combinatorial nature such as Maximum Flow, Hamiltonian Path, and various
other graph problems. His hobbies include playing soccer, video games, and the recorder,
the non-flute musical instrument that according to many, is also more pleasing to the ear.
T HEORY OF C OMPUTING, Volume 17 (5), 2021, pp. 1–27 27