Conditional Lower Bounds for All-Pairs Max-Flow∗
Robert Krauthgamer†
Ohad Trabelsi‡
Weizmann Institute of Science

arXiv:1702.05805v3 [cs.DS] 4 Feb 2018

February 6, 2018

Abstract
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(n3 ) even for sparse graphs, namely m = O(n); thus for general m, it
2
cannot be solved
√ significantly faster than O(n m). Since a single maximum st-flow can be solved
in time Õ(m n) [Lee and Sidford, FOCS 2014], we conclude that the all-pairs version might
require time equivalent to Ω̃(n3/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
Õ(m), then the runtime of Ω̃(n2 ) 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(n2 ) 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 n0 variables and m0 clauses
O(1) (1−δ)n0
can be solved in time m0
2
for a constant δ(ε) > 0, a problem for which not even
0
2n /poly(n0 ) 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(n3/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 edgedensity 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).
∗

This work was partially supported by the Israel Science Foundation grant #897/13 and by a Minerva Foundation grant. An extended abstract of this article appears in Proceedings of ICALP 2017 and is also available at
arXiv:1702.05805. The most significant difference is the addition of Section 4.
†
Email: robert.krauthgamer@weizmann.ac.il
‡
Email: ohad.trabelsi@weizmann.ac.il

1

1

Introduction

The maximum flow problem is one of the most fundamental problems in combinatorial optimization.
This classic problem and its variations such as minimum-cost flow, integral flow, and minimum-cost
circulation, were studied extensively over the past decades, and have become key algorithmic tools
with numerous applications, in theory and in practice. Moreover, techniques developed for flow
problems were generalized or adapted to other problems, see for example [BJS10, AMO93, AHK12].
The maximum st-flow problem, which we shall denote Max-Flow, asks to ship the maximum amount
of flow from a source node s to a sink node t in a directed edge-capacitated graph G = (V, E, w),
where throughout, we denote n = |V | and m = |E|, and assume integer capacities bounded by U .
After this problem was introduced in 1954 by Harris and Ross (see [Sch02] for a historical account),
Ford and Fulkerson [FF56] devised the first algorithm for Max-Flow, which runs in time O((n+m)F ),
where F is the maximum value of a feasible flow. Ever since, a long line of generalizations and
improvements was studied, and the current fastest algorithm for Max-Flow with arbitrary capacities
√
is by Lee and Sidford [LS14], which takes O(m n log U ) time. For the case of small capacities
and sufficiently sparse graphs, the fastest algorithm, due to Mądry [Mąd16], has a running time
Õ(m10/7 U 1/7 ). Here and throughout, Õ(f ) denotes O(f logc f ) for unspecified constant c > 0.
A very natural problem is to compute the maximum st-flow for multiple source-sink pairs in the
same graph G. The seminal work of Gomory and Hu [GH61] shows that in undirected graphs, MaxFlow for all n2 source-sink pairs requires at most n − 1 executions of Max-Flow (see also [Gus90],
where the n − 1 computations are all on the input graph), and a lot of research aimed to extend this
result to directed graphs, with several partial successes, see details in Section 1.1. However, it is
still not known how to solve Max-Flow for multiple source-sink pairs faster than solving it separately
for each pair, even in special cases like a single source and all possible sinks. We shall consider the
following problems involving multiple source-sink pairs, where the goal is always to report the value
of each flow (and not an actual flow attaining it).
Definition 1.1. (Single-Source Max-Flow) Given a directed edge-capacitated graph G = (V, E, w)
and a source node s ∈ V , output, for every t ∈ V , the maximum flow that can be shipped in G from
s to t.
Definition 1.2. (All-Pairs Max-Flow) Given a directed edge-capacitated graph G = (V, E, w), output,
for every pair of nodes u, v ∈ V , the maximum flow that can be shipped in G from u to v.
Definition 1.3. (ST-Max-Flow) Given a directed edge-capacitated graph G = (V, E, w) and two
subsets of nodes S, T ⊆ V , output, for every pair of nodes s ∈ S and t ∈ T , the maximum flow that
can be shipped in G from s to t.
Definition 1.4. (Global Max-Flow) Given a directed edge capacitated graph G = (V, E, w), output
the maximum among all pairs u, v ∈ V , of the maximum flow value that can be shipped in G from
u to v.
Definition 1.5. (Maximum Local Edge Connectivity) Given a directed graph G = (V, E), output the
maximum among all pairs u, v ∈ V , of the maximum number of edge-disjoint uv-paths in G.
Note that in a graph with all edge capacities equal to 1, the problem of finding the maximum
local edge connectivity is equivalent to finding the global maximum flow.

1.1

Prior Work

We start with undirected graphs, where the All-Pairs Max-Flow values can be represented in a very
succint manner, called nowdays a Gomory-Hu tree [GH61]. In addition to being very succint, it
2

Directed
No
No
No
Yes
Yes
Yes
Yes
Yes

Class
General
Uncapacitated Networks
Genus bounded by g
Sparse
Constant Treewidth
Uncapacitated
Uncapacitated DAG
Planar

Problem
All-Pairs (G-H Tree)
All-Pairs (G-H Tree)
All-Pairs (G-H Tree)
All-Pairs
All-Pairs
All-Pairs
Single-Source
Single-Source

Runtime
(n − 1)T (n, m)
Õ(mn)
2)
O(g
2
n log3 n
2
O(n + γ 4 log γ)
O(n2 )
O(mω )
O(nω−1 m)
O(n log3 n)

Reference
[GH61]
[KL02], [BHKP07]
[BENW16]
[ACZ98]
[ACZ98]
[CLL11]
[CLL11]
[LNSW12]

Table 1: Known algorithms for multiple-pairs Max-Flow. In this table, T (n, m) is the fastest time
to compute maximum st-flow in an undirected graph, ω is the matrix multiplication exponent, and
γ = γ(G) is a topological property of the input network that varies between 1 and Θ(n). In planar
graphs, γ is the minimum number of faces required to cover all the nodes (i.e., every node is adjacent
to at least one such face) over all possible planar embeddings [Fre95].

allows the flow values and the corresponding cuts (vertex partitions) to be quickly retrieved. For a
list of previous algorithms for multiple pairs maximum st-flow, see Table 1. For directed graphs, no
current algorithm computes the maximum flow between any k = ω(1) given pairs of nodes faster
than the time of O(k) separate Max-Flow computations. However, some results are known in special
settings. It is possible to compute Max-Flow for O(n) pairs in the time it takes for a single Max-Flow
computation [HO94] and this result is used to find a global minimum cut. However, these pairs
cannot be specified in the input.
For directed planar graphs, there is an O(n log3 n) time algorithm for the Single-Source MaxFlow problem [LNSW12], which immediately yields an O(n2 log3 n) time algorithm for the All-Pairs
version, that is much faster than the time of O(n2 ) computations of planar Max-Flow, a problem that
can be solved in time O(n log n) [BK09]. Based on these results, it was conjectured in [LNSW12]
that also in general graphs, All-Pairs Max-Flow can be solved faster than the time required for
computing O(n2 ) separate maximum st-flows.
Several hardness results are known for multiple-pairs variants of Max-Flow [AVY15]. For ST-Max√
Flow in sparse graphs (m = O(n)) and |S| = |T | = O( n), there is an n3/2−o(1) lower bound assuming at least one of the Strong Exponential Time Hypothesis (SETH), 3SUM, and All-Pairs ShortestPaths (APSP) conjectures is correct (for comprehensive surveys on them, see [Vas15, Vas18]). In
addition, they show that Single-Source Max-Flow on sparse graphs requires n2−o(1) time, unless
MAX-CNF-SAT can be solved in time 2(1−δ)n poly(m) for some fixed δ > 0, and in particular SETH
is false.
We will rely on SETH, a conjecture introduced by [IP01], and on some weaker assumption related
to its maximization version, MAX-CNF-SAT. In more detail, SETH states 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 poly(m), where poly(m) refers to O(mc ) for unspecified constant c. By the sparsification
lemma [IPZ01], in order to refute SETH it can be assumed that the number of clauses is O(n). The
MAX-CNF-SAT problem asks for the maximum number of clauses that can be satisfied in an input
CNF formula. Most of our conditional lower bounds are based on the assumption that for every fixed
δ > 0, MAX-CNF-SAT cannot be solved in time 2(1−δ)n poly(m), where currently even 2n /poly(n)
algorithms are not known for this problem [AVY15]. Note that this is a weaker assumption than
SETH, since a faster algorithm for MAX-CNF-SAT would imply a faster algorithm for CNF-SAT
3

and refute SETH. Different assumptions regarding the hardness of CNF-SAT have been the basis for
many lower bounds, including for the runtime of solving NP-hard problems exactly, parametrized
complexity, and problems in P. See the Introduction in [ABHS17] and the references therein.

1.2

Our Contribution

We present conditional runtime lower bounds for both uncapacitated and capacitated networks.
The proofs appear in sections 2 and 3, respectively, where the order reflects increasing level of
complication. All our lower bounds hold even when the input G is a DAG and has a constant
diameter, and in the case of general capacities, they can be easily modified to apply also for graphs
with constant maximum degree. In addition, for integer k ≥ 1 we use [k] to denote the range
{1, ..., k}.
Capacitated Networks Our main result is that for every set sizes |S| and |T |, the ST-Max-Flow
cannot be solved significantly faster than O(|S||T |m) (i.e., polynomially smaller runtime), unless a
breakthrough in MAX-CNF-SAT is achieved, and consequently in SETH.
Theorem 1.6. If for some fixed constants ε > 0, c1 , c2 ∈ [0, 1], ST-Max-Flow on graphs with n
nodes, |S| = Õ(nc1 ), |T | = Õ(nc2 ), m = O(n) edges, and capacities in [n] can be solved in time
O((|S||T |m)1−ε ), then for some δ(ε) > 0, MAX-CNF-SAT on n0 variables and O(n0 ) clauses can be
0
solved in time 2(1−δ)n poly(n0 ), and in particular SETH is false.
This result improves the aforementioned n3/2−o(1) lower bound of [AVY15], as for their setting
√
of |S| = |T | = O( n) our lower bound is n2−o(1) , although their lower bound is based on an
incomparable (and intuitively weaker) conjecture, that at least one of the SETH, 3SUM, and APSP
conjectures is correct. In fact, if there was a reduction from SETH that implied a larger runtime
lower bound for ST-Max-Flow, then the (single-pair) Max-Flow problem would require a strictly
super-linear time under it, but such a reduction is not possible unless the non-deterministic version
of SETH (abbreviated NSETH) is false [CGI+ 16]. And anyway, such a lower bound for Max-Flow
would be an amazing breakthrough.
The next theorem is an immediate corollary of Theorem 1.6, by assigning |S|, |T | = Θ(n).
Theorem 1.7. If for some fixed ε > 0, All-Pairs Max-Flow in graphs with n nodes, m = O(n) edges,
and capacities in [n] can be solved in time O((n2 m)1−ε ), then for some δ(ε) > 0, MAX-CNF-SAT
0
on n0 variables and O(n0 ) clauses can be solved in time 2(1−δ)n poly(n0 ), and in particular SETH is
false.
This conditional lower bound (see Figure 1) shows that All-Pairs Max-Flow requires time that is
equivalent to Ω(n3/2 ) computations of Max-Flow, which strongly separates the directed case from
the undirected one (where a Gomory-Hu tree can be constructed in the time of n − 1 computations).
If Max-Flow takes Õ(m) time, which is currently open but plausible, then the running time of Ω̃(n2 )
computations of Max-Flow is needed. This is in contrast to the aforementioned conjecture of Lacki,
Nussbaum, Sankowski, and Wulf-Nilsen [LNSW12] that All-Pairs Max-Flow in general graphs can be
solved faster than the time of O(n2 ) computations of maximum st-flow.
Uncapacitated Networks For the case of uncapacitated networks, we show that for every m =
m(n), All-Pairs Max-Flow cannot be solved significantly faster than O(mn). Here we introduce a
new technique to design reductions from SETH to graphs with varying edge densities, rather than
the usual reductions that only deal with sparse graphs.
4

Theorem 1.8. If for some fixed ε > 0 and c ∈ [1, 2], All-Pairs Max-Flow in uncapacitated graphs
with n nodes and m = Θ(nc ) edges can be solved in time O((mn1−ε )), then for some δ(ε) > 0,
0
MAX-CNF-SAT on n0 variables and O(n0 ) clauses can be solved in time 2(1−δ)n poly(n0 ), and in
particular SETH is false.
Hence, a certain additional improvement to the O(mω ) time algorithm of [CLL11] (and similarly
to the O(nω m) time for DAGs, where our lower bounds apply too) is not likely. We now present
conditional lower bounds for ST-Max-Flow, which are functions of |S| and |T |.
Theorem 1.9. If for some fixed constants ε > 0, c1 , c2 ∈ [0, 1], ST-Max-Flow on uncapacitated
graphs with n nodes, |S| = Õ(nc1 ), |T | = Õ(nc2 ), and O((|S| + |T |)n) edges can be solved in time
O((|S||T |n)1−ε ), then for some δ(ε) > 0, MAX-CNF-SAT on n0 variables and O(n0 ) clauses can be
0
solved in time 2(1−δ)n poly(n0 ), and in particular SETH is false.
n5

n5

Capacitated Networks

n4.5

n4.5

n4

n4

Time
Complexity

runtime of Θ(n2 ) executions
of Max-Flow using [LS14]

n3.5

Time
Complexity

Uncapacitated Networks
algorithm of [CLL11] for DAGs
when ω = 2.37 and ω = 2

algorithm of [CLL11] when
ω = 2.37 and ω = 2

n3.5

n3

n3
our lower bound

n2.5

n2.5

n2

our lower bound (which
applies also to DAGs)

n2
n

n

1.25

1.5

n
m = |E|

n

1.75

n

2

n

n1.25

n1.5
m = |E|

n1.75

n2

Figure 1: State of the art bounds for All-Pairs Max-Flow in directed networks. Conditional lower
bounds are depicted in dashed lines, and known algorithms in solid lines.
In addition, we present a conditional lower bound for computing the Maximum Local Edge
Connectivity of sparse graphs, which is the same as Global Max-Flow if all the capacities are 1, that
is indeed the case in our reduction. The next result, proved in Section 5, was obtained together
with Bundit Laekhanukit and Rajesh Chitnis, and we thank them for their permission to include it
here.
Theorem 1.10. If for some fixed ε > 0, the Maximum Local Edge Connectivity in graphs with n
nodes and Õ(n) edges can be found in time O(n2−ε ), then for some δ(ε) > 0, MAX-CNF-SAT on n0
0
variables and O(n0 ) clauses can be solved in time 2(1−δ)n poly(n0 ), and in particular SETH is false.
Generalization to Bounded Cuts Finally, we show in Section 4 that our lower bounds extend
to the version that requires to output the maximum-flow value only for source-sink pairs for which
this value is at most some given threshold k.

5

Connection to the Orthogonal Vectors Problem Our techniques are based on partitioning
the variable set of CNF-SAT to sets of different sizes, and constructing graphs with the property
that certain pairs of nodes would have smaller maximum flow between them if and only if they
correspond to a satisfying assignment. This approach is inspired by results of Williams [Wil05].
We remark that all of our theorems can also be proved assuming that for the appropriate
k ∈ {2, 3}, the k-Orthogonal Vectors (kOV) problem cannot be solved in time Õ(nk−ε ) for a fixed
constant ε > 0, in what is called the kOV Hypothesis (see [Vas15, Vas18]). In the kOV problem the
input is k sets {Ui }i∈[k] , each of n vectors from {0, 1}d , and the goal is to find k vectors {ui }i∈[k] ,
P Q
one from each set, such that u1 · ... · uk := di=1 kj=1 uj [i] = 0 (for k = 2 it means that u1 , u2
are orthogonal). An equivalent version of the problem has U1 = ... = Uk . Solving kOV in time
O(nk d) can be done easily by exhaustive search, while the fastest known algorithm for the problem
runs in time nk−1/Θ(log(d/ log n)) [AWY15, CW16]. Williams [Wil05] proved that SETH implies the
non-existence of an Õ(nk−ε )-time algorithm.

2

Reduction to Multiple-Pairs Max-Flow with Unit Capacity

In this section we prove Theorems 1.8 and 1.9. We start with a general lemma which is the heart
of the proofs.
Lemma 2.1. Let a ∈ [0, 1] and b ∈ [0, 1 − a]. Then MAX-CNF-SAT on n variables and m clauses
{Ci }i∈[m] can be reduced to O(m) instances of ST-Max-Flow with |S| = 2an and |T | = 2bn in graphs
with Θ(2an + 2(1−a−b)n m + 2bn ) nodes, Θ((2an + 2bn ) · 2(1−a−b)n m) edges, and capacities in {0, 1}.
Proof. Given a CNF-formula F on n variables and m clauses as input for MAX-CNF-SAT, a ∈ [0, 1],
and b ∈ [0, 1 − a], we split the variables into three sets U1 , U2 , and U3 , where U1 is of size an, U2
is of size (1 − a − b)n, and U3 is of size bn, and enumerate all their 2an , 2(1−a−b)n , and 2bn partial
assignments (with respect to F ), respectively, when the objective is to find a triple (α, β, γ) of
assignments to U1 , U2 , and U3 respectively, that satisfies the maximal number of clauses. We will
have an instance Gp of ST-Max-Flow for each value p ∈ [m], in which by one call to ST-Max-Flow
we check if there exists a triple α, β, and γ that satisfies at least p clauses, as follows.
We construct a graph Gp for every p ∈ [m] on N nodes V1 ∪ V2 ∪ V3 , where V1 contains a node
α for every assignment α to U1 , V2 contains 2m + 1 + (p − 1) = 2m + p nodes for every assignment
β to U2 , that are βil and βir for every i ∈ [m], β 0 , and the set {βi0 }i∈[p−1] , and V3 contains a node γ
for every assignment γ to U3 . We use the notation α for nodes in V1 and for assignments to U1 , β
for assignments to U2 , and γ for nodes in V3 and assignments to U3 . However, it will be clear from
the context. Now, we have to describe the edges in the network. In order to simplify the reduction,
we partition the edges into blue and red colors, as follows.
For every α, β, and i ∈ [m], we add a blue edge from α to βil if both of α and β do not satisfy
the clause Ci (do not set any of the literals to true), and otherwise we add a red edge from α to βir .
We further add, for every β, γ, and i ∈ [m], a blue edge from βil to γ if γ does not satisfy Ci . For
every β, γ, and j ∈ [p − 1], we add a red edge from every βj0 to every γ. For every β and i ∈ [m],
we add a red edge from βil to βir and from βir to β 0 , and finally for every β and j ∈ [p − 1], we add
a red edge from β 0 to βj0 , where all edges are of capacity 1.
The graph we built has 2an + 2 · 2(1−a−b)n m + 2(1−a−b)n + 2(1−a−b)n (p − 1) + 2bn = Θ(2an +
(1−a−b)n
2
m + 2bn ) nodes, 2an · 2(1−a−b)n m + 2bn · 2(1−a−b)n m + 2 · 2(1−a−b)n m+ (p − 1)2(1−a−b)n +
2bn · (p − 1)2(1−a−b)n = Θ((2an + 2bn ) · 2(1−a−b)n m) edges, with capacities in {0, 1} (see Figure 2),
and its construction time is asymptotically the same as the time it takes to output its edge set.
For every α, β, and γ, we denote by Gα,β,γ
the graph induced from Gp on the nodes
p
6

β 01

β0

β1r
β1l

α

β2l

β 02

β2r
β3r

γ

β3l

β̃ 01

β̃

β̃1r

α̃
β̃1l
β̃2l

0

β̃ 02

γ̃

β̃2r
β̃3r

β̃3l

Figure 2: An illustration of part of the reduction. Here, U1 , U2 , and U3 have 2 assignments each,
α and α̃ to U1 , β and β̃ to U2 , and γ and γ̃ to U3 . Blue edges are dashed. For simplicity, only the
β̃,γ̃
are presented. In this illustration, α does not satisfy anything, β satisfies
edges of G3α,β,γ̃ ∪ Gα,
3
C2 and C3 , β̃ satisfies C1 , and γ̃ satisfies C1 . Note that the assignment comprised of α, β, and γ̃
satisfies all the clauses, and indeed the maximum flow from α to γ is 2 · 3 − 1 = 5.

!
(α, β 0 , γ) ∪

βiy

[
y∈{l,r}
i∈[m]

!
∪

[

βj0

j∈[p−1]

We claim that for every α and γ, the maximum flow from α to γ can be bounded by the sum,
over all β, of the maximum flow between them in Gα,β,γ
. This claim follow easily because the
p
α,β1 ,γ
α,β2 ,γ
forβ1 6= β2 is exactly the source and the sink {α, γ}, no edge passes
intersection Gp
∩ Gp
S α,β,γ
between these two graphs, and
consists of all nodes that are both reachable from α
β Gi
and γ is reachable from them.
We now prove that if there is an assignment to F that satisfies at least p clauses then the graph
Gp we built has a triple α, β, γ with maximum flow from α to γ in Gα,β,γ
at most m − 1. Since
p
β̃,γ
for every β̃, m is the number of outgoing edges from α in Gα,
, m is also an upper bound for the
p
maximum flow from α to γ in it, and hence in Gp it is at most 2(1−a−b)n m − 1. Otherwise, we will
show that every triple α, β, γ has a maximum flow from α to γ in Gα,β,γ
of size at least m, and so in
p
(1−a−b)n
Gp it is at least 2
m. Hence, by simply picking the maximal j ∈ [m] such that the maximum
flow in Gj of some pair α, γ is at most 2(1−a−b)n m − 1, and then by iterating over all assignments
β to U2 with α and γ fixed as the assignments to U1 and U3 , we can also find the required triple
α, β, γ.
For the first direction, assume that F has an assignment that satisfies at least p clauses, and
denote such assignment by Φ. Let αΦ , βΦ , and γΦ be the assignments to U1 , U2 , and U3 , respectively,

7

that are induced from Φ. Since a blue path from αΦ through βΦ li for some i ∈ [m] to γΦ corresponds
to αΦ , βΦ , and γΦ all do not satisfy Ci , in Gαp Φ ,βΦ ,γΦ there are at most m − p (internally) disjoint
blue paths from α to γ. As the only way to ship flow in Gαp Φ ,βΦ ,γΦ that is not through a blue path
0 , and the total number of edges going out of this node is p − 1, we conclude
is through the node βΦ
that the total maximum flow in GpαΦ ,βΦ ,γΦ from αΦ to βΦ is bounded by m − p + (p − 1) = m − 1.
Since for every β, the maximum amount of flow that can be shipped in Gαp Φ ,β,γΦ from αΦ to γΦ
is at most m, summing over all β we get that the total flow in Gp from αΦ to γΦ is bounded by
(2(1−a−b)n − 1)m + (m − 1) ≤ 2(1−a−b)n m − 1, as required.
For the second direction, assume that every assignment to F satisfies at most p − 1 clauses. In
order to show that the maximum flow from every α to every γ is at least 2(1−a−b)n m, we first fix α,
β, and γ. Then, by passing flow in two phases we show that m units of flow can be passed in Gα,β,γ
p
from α to γ. As this argument applies for every β, we can add up the respective flows without
violating capacities, concluding the proof. By the assumption, there exist m − (p − 1) = m − p + 1
i’s, such that α, β, and γ do not satisfy Ci , and we denote a set with this amount of such i’s
by Iβ . Each of these i’s induces a blue path (α → βil → γ) from α to γ in Gα,β,γ
, and so we
p
ship a unit of flow through every one of them according to Iβ , in what we call the first phase. In
the second phase, we ship additional m − (m − p + 1) = p − 1 units in the following way. Let
A1 := {i ∈ [m] \ Iβ : α 2 Ci ∧ β 2 Ci }, and A2 := ([m] \ Iβ ) \ A1 = {i ∈ [m] \ Iβ : α  Ci ∨ β  Ci },
where α  Ci denotes that the assignment α satisfies Ci (as defined earlier), and α 2 Ci denotes
that it does not satisfy Ci . Let f : A1 ∪ A2 → [m − |Iβ |] be a bijective function such that the range
of A1 is [|A1 |] and the range of A2 is [m − |Iβ |] \ [|A1 |]. Clearly, there exists such bijection and it is
easy to find one. For every i ∈ A1 we ship flow through the path (α → βil → βir → β 0 → βj0 → γ),
and for every i ∈ A2 through the path (α → βir → β 0 → βj0 → γ), in both cases with j = f (i).
Since we defined the flow in paths, we only need to show that the capacity requirements hold,
and we start with blue edges. Indeed, edges of the form (α, βil ) are used in the first phase, with flow
that is determined uniquely by β and i ∈ Iβ , and in the second phase uniquely according to β and
i ∈ [m] \ Iβ , and so they cannot be used twice. Edges of the form (βil , γ) are only used in the first
phase, and their flow is uniquely determined according to β and i ∈ Iβ , and so are good too. We
now proceed to red edges, which were used only in the second phase.
Edges of the forms (α, βir ), (βil , βir ) and (βir , β 0 ) have flow that is uniquely determined by β and
i ∈ [m] \ Iβ , and so are not used more than once. Edges of the form (β 0 , βj0 ) have flow that is
uniquely determined by β and j = f (i) ∈ [p − 1], and since f is a bijection, every j has at most one
i such that f (i) = j, and so these edges are also used at most once. As a byproduct, and since every
edge of the form (βj0 , γ) has only the edge (β 0 , βj0 ) as its source for flow, edges of the form (βj0 , γ)
are also used at most once. Altogether, we have bounded the total flow in all edges that were used
in both phases, and so the capacity requirements follow, which completes the proof of the second
direction and of Lemma 2.1.
Proof of Theorem 1.8. We apply Lemma 2.1 in as follows. For every setting of a = b ∈ [1/3, 1/2]
we get graphs G = (V, E, w) with |V | = Θ(2an ) (|V | = Θ(2an )m if a = 1/3) and |E| = 2(1−a)n m.
Hence, |E| = O(|V |1/a−1 ) and so in order to get any c ∈ [1, 2] we can pick a(= b) such that
additionally c = 1/a − 1, and Theorem 1.8 follows.
Proof of Theorem 1.9. Here we apply Lemma 2.1 a bit differently. For every setting of a, b ∈ [0, 1/2]
such that 1 − a − b ≥ max(a, b) we get graphs G = (V, E, w) with |V | = Θ(2(1−a−b)n m) and
|E| = Θ((2an + 2bn )2(1−a−b)n m). Hence, in order to get any c1 , c2 ∈ [0, 1], we can pick a, b such that
additionally c1 = a/(1−a−b) and c2 = b/(1−a−b), and thus |S| = (|V |/m)c1 and |T | = (|V |/m)c2 ,
and so we get our lower bound for |E| = O((|S| + |T |)|V |) and Theorem 1.9 follows.
8

3

Reduction to Multiple-Pairs Max-Flow in Capacitated Networks

In this section we prove Theorems 1.6 and 1.7. We proceed to prove our main technical lemma.
Lemma 3.1. Let a ∈ [0, 1] and b ∈ [0, 1 − a]. Then MAX-CNF-SAT on n variables and m clauses
{Ci }i∈[m] can be reduced to O(m) instances of ST-Max-Flow with |S| = 2an and |T | = 2bn in graphs
with N = Θ(2an + 2(1−a−b)n m + 2bn ) nodes, O((2an + 2(1−a−b)n + 2bn )m) = O(N ) edges, and with
capacities in [N ].
Proof. Given a CNF-formula F on n variables and m clauses as input for MAX-CNF-SAT, a ∈ [0, 1],
and b ∈ [0, 1 − a], we begin similarly to before by splitting the variables into three sets U1 , U2 , and
U3 where U1 is of size an, U2 is of size (1 − a − b)n, and U3 is of size bn, and enumerate all their
2an , 2(1−a−b)n , and 2bn partial assignments (with respect to F ), respectively, when the objective
is to find a triple (α, β, γ) of assignments to U1 , U2 , and U3 , that satisfy the maximal number of
clauses. We will have an instance Gp of ST-Max-Flow for each value p ∈ [m], in which by one call
to ST-Max-Flow we check if there exists a triple (α, β, γ) that satisfies at least p clauses, as follows.
We construct the graph Gp on N nodes V1 ∪ V2 ∪ V3 ∪ A ∪ B ∪ {vB }, where V1 contains a node
α for every assignment α to U1 , V2 contains 3m + 1 nodes for every assignment β to U2 , that are
βil , βic , βir , for every i ∈ [m], and β 0 , V3 contains a node γ for every assignment γ to U3 , A contains
two nodes Ci and Ci2 for every clause Ci , and B contains a node Ci for every clause Ci . We use the
notation α for nodes in V1 and assignments to U1 , β to assignments to U2 , γ for nodes in V3 and
assignments to U3 , and Ci for nodes in B and clauses. However, it will be clear from the context.
Now, we have to describe the edges in the network. In order to simplify the reduction, we partition
the edges into red and blue colors, as follows.
For every α and i ∈ [m] we add a red edge of capacity 2(1−a−b)n from α to Ci if α  Ci , and a
blue edge of the same capacity from α to Ci2 otherwise. We further add, for every β, a red edge of
capacity 1 from Ci to βic , a blue edge of capacity 1 from Ci2 to βil , a blue edge of capacity 1 from
βil to βir if β 2 Ci , a red edge of capacity 1 from βic to β 0 , and a blue edge of capacity 1 from βir to
Ci . For every β we add a red edge of capacity p − 1 from β 0 to vB . For every γ we add a red edge
of capacity 2(1−a−b)n (p − 1) from vB to γ ∈ V3 , and finally, for every γ and i ∈ [m] we add a blue
edge of capacity 2(1−a−b)n from Ci to γ if γ 2 Ci .
The graph we built has N = 2an + 2m + 2(1−a−b)n · 3m + 2(1−a−b)n + 1 + m + 2bn = Θ(2an +
2(1−a−b)n · m + 2bn ) nodes, at most 2an m + 2(1−a−b)n · 2m + 2(1−a−b)n · 2m + 2(1−a−b)n m + 2(1−a−b)n +
1 + 2(1−a−b)n m + 2bn m = O((2an + 2(1−a−b)n + 2bn )m) edges, all of its capacities are in [N ], and its
construction time is O(N m) (see Figure 3).
We proceed to prove that if there is an assignment to F that satisfies at least p clauses then the
graph Gp we built has a pair α, γ with maximum flow from α to γ at most 2(1−a−b)n m − 1, and
otherwise, every α, γ has a maximum flow of size at least 2(1−a−b)n m. Hence, by simply picking the
maximal j ∈ [m] such that the maximum flow in Gj of some pair α, γ is at most 2(1−a−b)n m − 1,
and then by iterating over all assignments β to U2 with α and γ fixed as the assignments to U1 and
U3 , we can also find the required triple α, β, γ.
For the first direction, assume that F has an assignment that satisfies at least p clauses, and
denote such assignment by Φ. Let αΦ , βΦ , and γΦ be the assignments to U1 , U2 , and U3 , respectively,
that are induced from Φ. We will show that there exists an (αΦ , γΦ ) cut whose capacity is at most
2(1−a−b)n m − 1, hence by the Min-Cut Max-Flow theorem, the maximum flow from αΦ to γΦ is
bounded by this number, concluding the proof of the first direction. We define the cut in a way
9

p − 1 (= 2)

β0

vB

β1c

n
b)

2)
1(
=
p−
C2

γ

β̃ 0

C22
β̃1c

(=

2(1−a−

2)

α̃

4)

2)

(=

C2

2)

(=

β3r

(=

a−
−
(1

2

a−
b)n

n
b)

β3l

2 (1−

n
b)
a−
−
(1

C12

2

·2

2)

C1

β3c

a−
−
(1

α

(=

β2r

2

b)n
a−
(1−

β2l

1)

β1r
β2c

C1

−
(p

β1l

C3

β̃1l

β̃1r

C3

b)n

(= 2)

γ̃

β̃2c

C32
β̃2l

β̃2r
β̃3c

β̃3l

β̃3r

Figure 3: An illustration of part of the reduction, with p = m. Here, U1 , U2 , and U3 have 2
assignments each; α and α̃ to U1 , β and β̃ to U2 , γ and γ̃ to U3 . Bolder edges correspond to edges
of higher capacity (specified wherever they are bigger than 1), and blue edges are dashed. For
simplicity, only the edges relevant to α and γ̃ are presented. In this illustration, α satisfies C3 , β
satisfies C1 , β̃ satisfies C3 , and γ̃ satisfies C2 . Note that the assignment comprised of α, β, and γ̃
satisfies all the clauses, and indeed the maximum flow from α to γ is 2 · 3 − 1 = 5.
that for every β 6= βΦ , the cut will have m cut edges that are contributed from nodes related to β,
and nodes related to βΦ will be carefully added to either side of the cut, so that they will contribute
capacity of only m − 1 to the cut. This is done by exploiting the fact that there are at most m − p
blue paths from αΦ to γΦ through nodes associated with βΦ . To be more precise, we define a
suitable cut as follows.
0
S = {αΦ , βΦ
} ∪ {Ci : αΦ  Ci } ∪ {Ci2 : αΦ 2 Ci } ∪ {βΦ ci : i ∈ [m]} ∪ {Ci , βΦ li , βΦ ri : γΦ  Ci }∪

{βΦ li : γΦ 2 Ci ∧ βΦ  Ci }

Claim 3.2. The cut (S, V \ S) = (S, T ) has capacity 2(1−a−b)n m − 1.
Proof of Claim. We will go over all the nodes in S, and count the total capacity leaving to nodes in
T for each of them. αΦ ∈ S and all nodes Ci and Ci2 that are adjacent to it are in S too, hence it
10

does not contribute anything. For every i ∈ [m], we have two cases for nodes in A. If αΦ  Ci then
Ci2 ∈ T and hence Ci2 does not contribute anything. However, Ci has 2(1−a−b)n outgoing edges,
where all except βΦ ci are in T . Hence, it contributes 2(1−a−b)n − 1 to the cut. Else, if αΦ 2 Ci then
Ci ∈ T and hence Ci does not contribute anything. But Ci2 has 2(1−a−b)n outgoing edges, of which
2(1−a−b)n − 1 are cut edges as their targets are in T , and the one incoming to βΦ li is a cut edge if
and only if βΦ i 2 Ci and also γΦ 2 Ci (equivalently, βΦ li ∈ T ), and in our current case it means that
Φ 2 Ci . Hence, for every i ∈ [m], the nodes in {Ci , Ci2 } contribute 2(1−a−b)n −1 to the cut if Φ  Ci ,
and 2(1−a−b)n otherwise. Since there are at most m − p clauses that are not satisfied by Φ, summing
over all i ∈ [m] would yield a total of at most p(2(1−a−b)n − 1) + (m − p)(2(1−a−b)n ) = 2(1−a−b)n m − p
cut edges for vertices with origin in A.
For every β 6= βΦ , all nodes in V2 that are associated with β, vB , and γΦ , are in T and hence will
not contribute anything to the cut. However, the node βΦ 0 is always in S, with vB its sole target,
and hence the edge (βΦ 0 , vB ) is in the cut and βΦ 0 contributes an additional amount of p − 1, to a
current total of at most 2(1−a−b)n m − p + (p − 1) = 2(1−a−b)n m − 1. In addition, βΦ 0 is the only
target of βΦ ci , and thus βΦ ci will not contribute to the cut.
l and β l , and
We will show that the rest of the nodes, i.e., nodes in V2 that are of the forms βΦ
Φ
l
the nodes in B, contribute nothing to the cut. For every i ∈ [m], βΦ i ∈ S if and only if either
βΦ  Ci or γΦ  Ci , so we assume that. It always happens that βΦ ci ∈ S, and βΦ ri ∈ T if and only
if γΦ 2 Ci , but in such case, by our assumption it must be that βΦ  Ci , which implies that the
edge (βΦ li , βΦ ri ) is not in the graph, thus the total contribution of βΦ li is zero. Continuing to nodes
of the forms βΦ ri and Ci , it is easy to verify that the following four statements are either all true or
all false: βΦ ri ∈ S, γΦ  Ci , Ci ∈ S, and the edge (Ci , γΦ ) is not in the graph. In the case where
they all false, in particular Ci and βΦ ri are in T and it is clear that they do not contribute anything,
so we will focus on the remaining case. Since Ci is in S and is the only target of βΦ ri , βΦ ri will
not increase the cut capacity. In addition, since the edge (Ci , γΦ ) is not in the graph, Ci does not
increase the capacity of the cut either. Altogether we have bounded the total capacity of the cut
by 2(1−a−b)n m − 1, finishing the proof of Claim 3.2.
Proceeding with the proof of Lemma 3.1, we now focus on the second direction. Assume that
every assignment to F satisfies at most p − 1 clauses. We remind that we need to prove that the
maximum flow from every α to every γ is at least 2(1−a−b)n m, and to do this we first fix α and γ.
By the assumption, for every β there exist m − (p − 1) = m − p + 1 i’s, such that α, β, and γ do
not satisfy Ci , and we denote a set with this amount of such i’s by Iβ . Each of these i’s induces
a blue path (α → Ci2 → βil → βir → Ci → γ) from α to γ, and so we pass a unit of flow through
every one of them according to Iβ , and for all β, in what we call the first phase. We note that so
far, the flow sums up to 2(1−a−b)n (m − p + 1), and so we carry on with shipping the second phase
of flow through paths that are not entirely blue.
We claim that for every β, we can pass an additional amount of m − (m − p + 1) = p − 1 units
through β 0 , which would add up to a total flow of 2(1−a−b)n (m−p+1)+2(1−a−b)n (p−1) = 2(1−a−b)n m,
concluding the proof. Indeed, for every β, we ship flow in the following way. For every i ∈ [m] \ Iβ ,
if α 2 Ci then send a unit through (α → Ci2 → βil → βic → β 0 → vB → γ), and otherwise send a
unit through (α → Ci → βic → β 0 → vB → γ).
Since we defined the flow in paths, we only need to show that the capacity constraints are
satisfied, starting with edges of color blue. Edges of the forms (βil , βir ), (βir , Ci ), and (Ci , γ) are
only used in the first phase, where the flow in the first two is uniquely determined by β and i ∈ Iβ ,
and so at most 1 unit of flow is passed through them, and the flow in the latter kind is determined
by i ∈ Iβ , and the same i ∈ Iβ can have at most |{βir }β | = 2(1−a−b)n units of flow passing in
(Ci , γ), and so the flow in it is also bounded. The flow in edges of the form (Ci2 , βil ) in the first
11

phase is uniquely determined by β and i ∈ Iβ , and in the second phase uniquely according to β and
i ∈ [m] \ Iβ , and so will not be used twice, and the flow in edges of the form (α, Ci2 ) is determined
in
second phase by i ∈ [m] \ Iβ , and so will be used at most
P the first phase
P by i ∈ Iβ and in the (1−a−b)n
|I
∩
{i}|
+
|([m]
\
I
)
∩
{i}|
≤
2
times.
β
β β
β
We now proceed to prove that red edges too do not have more flow than their capacity, and for
this we only need to consider the second phase. Edges of the forms (Ci , βic ), (βil , βic ), and (βic , β 0 )
have flow that is uniquely determined by β and i ∈ [m]\Iβ and so are not used more than once, edges
of the form (β 0 , vB ) have flow that is determined by β and thus have flow |{βic }i∈[m]\Iβ | = |[m]\Iβ | =
p − 1, and edges of the form (vB , γ) have flow of size (p − 1)|{β 0 }β |2(1−a−b)n = (p − 1)2(1−a−b)n ,
and hence are properly bounded. Finally, edges of the form (α, Ci ) have flow that is determined by
i ∈ [m] \ Iβ and so are used at most |{βic }β | = 2(1−a−b)n times. Altogether, we have bounded the
total flow in all the edges that were used in both phases, and so the capacity requirements follow,
which completes the proof of the second direction and of Lemma 3.1.
Proof of Theorem 1.6. We apply Lemma 3.1 in the following way. For every setting of a, b ∈ [0, 1/2]
such that 1 − a − b ≥ max(a, b) we get graphs G = (V, E, w) with |V | = Θ(2(1−a−b)n m) and
|E| = Θ(2(1−a−b)n m) = O(|V |). Hence, in order to get any c1 , c2 ∈ [0, 1], we can pick a, b such that
additionally c1 = a/(1−a−b) and c2 = b/(1−a−b), and thus |S| = (|V |/m)c1 and |T | = (|V |/m)c2 ,
and so our claimed lower bound and Theorem 1.6 follow.

4

Generalization to Bounded Cuts

Our lower bounds extend to the version where we only care about vertex-pairs with maximum flow
bounded by a given k, which we refer to as kPMF.
Definition 4.1. (kPMF) Given a directed edge-capacitated graph G = (V, E, w) and an integer k,
for every pair of nodes u, v ∈ V where the maximum flow that can be shipped in G from u to v is of
size at most k, output this pair and its maximum flow value.
Theorem 4.2 (Generalization of Theorem 1.8). If for some fixed constants ε > 0 and c ∈ [0, 1],
kPMF in uncapacitated graphs with n nodes, k = Õ(nc ), and m = O(kn) edges can be solved in
time O((n2 k)1−ε ), then for some δ(ε) > 0, MAX-CNF-SAT on n0 variables and O(n0 ) clauses can
0
be solved in time 2(1−δ)n poly(n0 ), and in particular SETH is false.
Proof. We apply Lemma 2.1 as follows. For every setting of a = b ∈ [1/3, 1/2] we get graphs G =
(V, E, w) with |V | = Θ(2an ) (|V | = Θ(2an m) if a = 1/3), and |E| = 2an · 2(1−2a)n m = Θ(2(1−a)n m).
The main idea is that the middle layer bound the flow from every α to every γ, which are the only
pairs that we need to find the maximum flow for. To be more precise, for every α0 and γ 0 we show
a cut of capacity k = O(2(1−2a)n m) separating them, by considering
S = {α0 } ∪ {βil : i ∈ [m], ∀β}.
Clearly, the only outgoing edges from S are from α0 and from vertices of the form βil . α0 has an
outgoing degree at most O(2(1−2a)n m), and for each β and i ∈ [m], vertices of the form βil have a total
outgoing degree at most 2. Hence, the total capacity of the cut is bounded by k = O(2(1−2a)n m).
The claimed range of k is attained because setting a = 1/2 yields k = O(m) = O(log|V |) ≤ O(nc ),
and letting a approach 1/3 yields k tending to O(2n/3 m) = O(|V |). Note that |E| = O(|V |k), and
|V |2 k = O((2an )2 · 2(1−2a)n m) = O(2n m), and finally in order to get any c ∈ [0, 1] we can pick
a(= b) such that additionally c = 1/a − 2, and Theorem 4.2 holds.
12

Theorem 4.3 (Generalization of Theorem 1.7). If for some fixed constants ε > 0 and c ∈ [0, 1],
kPMF in graphs with n nodes, k = Õ(nc ), m = O(n) edges, and capacities in [n] can be solved in
time O((n2 k)1−ε ), then for some δ(ε) > 0, MAX-CNF-SAT on n0 variables and O(n0 ) clauses can
0
be solved in time 2(1−δ)n poly(n0 ), and in particular SETH is false.
Proof. We apply Lemma 3.1 in a similar fashion to the application of Lemma 2.1 in the proof of
Theorem 4.2, where the choices of a and b are done in exactly the same way as before, also allowing
again a free choice of c ∈ [0, 1]. However, now |E| = O(|V |), and we choose the cut as follows. For
every α0 and γ 0 we show a cut of capacity k = O(2(1−2a)n m) separating them, by considering
S = {α0 } ∪ {Ci , Ci2 : i ∈ [m]} ∪ {βil , βic : i ∈ [m], ∀β}.

Clearly, the only outgoing edges from S are of capacity 1, from α0 and from vertices of the forms
and βic . For each β and i ∈ [m], these vertices have a total of at most 2 edges going out to the
rest of the graph. Hence, the size of the cut is bounded by k = O(2(1−2a)n m), and the range of k is
similar to the proof of Theorem 4.2, and so Theorem 4.3 holds.

βil

√
Known algorithms solve kPMF in directed graphs in time Õ(n2 m · min(k, n)), which is bigger
√
than the lower bound in Theorem 4.3 by a factor that is roughly between n and n for sparse
graphs, leaving a gap that is not too big even for relatively small values of k. This running time can
be achieved by O(n2 ) computations of either the aforementioned O(mk) time algorithm of [FF56]
√
(actually, a slightly modified version that halts when the total flow exceeds k), or the Õ(m n) time
algorithm of [LS14].
It is interesting to note that in graphs that are undirected and uncapacitated, an algorithm for
kPMF with running time O(mk + n2 ) was shown in [BHKP07]. This shows a separation between the
directed and the undirected cases also for uncapacitated graphs, roughly by a factor Ω(n2 k/(mk +
n2 )) = Ω(min(k, n/k)), since our relevant conditional lower bound is proved for m = O(kn). Their
algorithm actually builds in time O(mk) a partial Gomory-Hu tree that succinctly represents the
values required by kPMF, and then it is easy to extract all the relevant values in time O(n2 ), as
√
required by our definition of kPMF. For instance, when k = O( n) and m = O(n3/2 ) their upper
bound for the undirected and uncapacitated case is O(n2 ), while our lower bound for the directed
case is n2.5−o(1) .

5

Global Max-Flow

Proof of Theorem 1.10. Given a CNF-formula F on n variables and m clauses {Ci }i∈[m] as input
for MAX-CNF-SAT, we split the variables into two sets U1 and U2 of size n/2 each and enumerate
all 2n/2 partial assignments (with respect to F ) to each of them, when the objective is to find a
pair (α, β) of assignments to U1 and U2 that satisfy the maximal number of clauses. We construct a
graph G = (V, E) such that V = L ∪ R ∪ C as follows. L contains a node α for every assignment α
to U1 , R contains a node β for every assignment β to U2 , and C contains three nodes c0,0 , c0,1 , and
c1,0 for every clause Ci . We use the notation α for nodes in L and assignments to U1 , β for nodes
in R and assignments to U2 . However, it will be clear from the context. For every assignment α
to U1 and clause Ci , we add an edge from α to c, and c,2 if α  Ci , and an edge from α to c2,
otherwise. Similarly, for every assignment β to U2 and clause Ci , we add an edge from β to c, and
c2, if β  Ci , and an edge from β to c,2 otherwise. This graph has N = n + n + 3m = O(n) nodes
and at most n · 2m + n · 2m = Õ(n) edges. For every pair of assignments α and β and clause Ci
there is exactly one path (of length 2) from α to β through nodes associated with Ci if and only if
13

both α  Ci and β  Ci , and no paths through them otherwise. Hence, the number of edge disjoint
paths from α to β is exactly the number of clauses that are satisfied by both of the assignments α
and β, and so an algorithm for Maximum Local Edge Connectivity with running time Õ(n2−ε ) implies
an algorithm for MAX-CNF-SAT with running time Õ((2n/2 )2−ε ) = Õ(2(1−ε/2)n ), completing the
proof for δ(ε) = ε/2.
Acknowledgements We thank Rajesh Chitnis and Bundit Laekhanukit for some useful conversations, and for their part in achieving the result on Global Max-Flow.

References
[ABHS17] A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay. SETH-based lower bounds
for subset sum and bicriteria path. CoRR, 2017. Available from: http://arxiv.org/
abs/1704.04546.
[ACZ98]

S. R. Arikati, S. Chaudhuri, and C. D. Zaroliagis. All-pairs min-cut in sparse networks.
J. Algorithms, 29(1):82–110, 1998. doi:10.1006/jagm.1998.0961.

[AHK12]

S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a metaalgorithm and applications. Theory of Computing, 8(1):121–164, 2012. doi:10.4086/
toc.2012.v008a006.

[AMO93]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows - theory, algorithms and
applications. Prentice Hall, 1993.

[AVY15]

A. Abboud, V. Vassilevska-Williams, and H. Yu. Matching triangles and basing hardness
on an extremely popular conjecture. In Proceedings of the Forty-seventh Annual ACM
Symposium on Theory of Computing, STOC ’15, pages 41–50. ACM, 2015. doi:10.
1145/2746539.2746594.

[AWY15]

A. Abboud, R. Williams, and H. Yu. More applications of the polynomial method to
algorithm design. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA ’15, pages 218–230, 2015. doi:10.1145/2722129.2722146.

[BENW16] G. Borradaile, D. Eppstein, A. Nayyeri, and C. Wulff-Nilsen. All-pairs minimum cuts
in near-linear time for surface-embedded graphs. In 32nd International Symposium on
Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:16. Schloss Dagstuhl–Leibniz-Zentrum fuer
Informatik, 2016. doi:10.4230/LIPIcs.SoCG.2016.22.
[BHKP07] A. Bhalgat, R. Hariharan, T. Kavitha, and D. Panigrahi. An Õ(mn) Gomory-Hu tree
construction algorithm for unweighted graphs. In 39th Annual ACM Symposium on
Theory of Computing, STOC’07, pages 605–614. ACM, 2007. doi:10.1145/1250790.
1250879.
[BJS10]

M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali. Linear Programming and Network Flows.
John Wiley & Sons, Inc., fourth edition, 2010.

[BK09]

G. Borradaile and P. Klein. An Õ(n log n) algorithm for maximum st-flow in a directed
planar graph. J. ACM, 56(2):9:1–9:30, 2009. doi:10.1145/1502793.1502798.

14

[CGI+ 16]

M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider.
Nondeterministic extensions of the strong exponential time hypothesis and consequences
for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in
Theoretical Computer Science, ITCS ’16, pages 261–270. ACM, 2016. doi:10.1145/
2840728.2840746.

[CLL11]

H. Y. Cheung, L. C. Lau, and K. M. Leung. Graph connectivities, network coding,
and expander graphs. In Proceedings of the 2011 IEEE 52nd Annual Symposium on
Foundations of Computer Science, FOCS ’11, pages 190–199. IEEE Computer Society,
2011. doi:10.1109/FOCS.2011.55.

[CW16]

T. M. Chan and R. Williams. Deterministic apsp, orthogonal vectors, and more: Quickly
derandomizing razborov-smolensky. In Proceedings of the Twenty-seventh Annual ACMSIAM Symposium on Discrete Algorithms, SODA ’16, pages 1246–1255, 2016. doi:
10.1145/2884435.2884522.

[FF56]

L. R. Ford, Jr. and D. R. Fulkerson. Maximal flow through a network. Canadian Journal
of Mathematics, 8:399–404, 1956. doi:10.4153/CJM-1956-045-5.

[Fre95]

G. N. Frederickson. Using cellular graph embeddings in solving all pairs shortest paths
problems. J. Algorithms, 19(1):45–85, 1995. doi:10.1006/jagm.1995.1027.

[GH61]

R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society for
Industrial and Applied Mathematics, 9:551–570, 1961. doi:10.1137/0109047.

[Gus90]

D. Gusfield. Very simple methods for all pairs network flow analysis. SIAM J. Comput.,
19(1):143–155, 1990. doi:10.1137/0219009.

[HO94]

J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed
graph. J. Algorithms, 17(3):424–446, 1994. doi:10.1006/jagm.1994.1043.

[IP01]

R. Impagliazzo and R. Paturi. On the complexity of k-SAT. Journal of Computer and
System Sciences, 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727.

[IPZ01]

R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential
complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001. doi:
10.1006/jcss.2001.1774.

[KL02]

D. R. Karger and M. S. Levine. Random sampling in residual graphs. In Proceedings of
the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC ’02, pages
63–66, New York, NY, USA, 2002. ACM. doi:10.1145/509907.509918.

[LNSW12] J. Lacki, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. Single source – all sinks
max flows in planar digraphs. In Proceedings of the 53rd IEEE Annual Symposium on
Foundations of Computer Science, FOCS ’12, pages 599–608. IEEE Computer Society,
2012. doi:10.1109/FOCS.2012.66.
[LS14]

Y. T. Lee and A. Sidford.
Path finding methods for linear programming: Solving
√
linear programs in Õ( rank) iterations and faster algorithms for maximum flow. In
Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer
Science, FOCS ’14, pages 424–433. IEEE Computer Society, 2014. doi:10.1109/FOCS.
2014.52.
15

[Mąd16]

A. Mądry. Computing maximum flow with augmenting electrical flows. In Proceedings
of the 57th IEEE Annual Symposium on Foundations of Computer Science, FOCS ’16,
pages 593–602. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.70.

[Sch02]

A. Schrijver. On the history of the transportation and maximum flow problems. Math.
Program., 91(3):437–445, 2002. doi:10.1007/s101070100259.

[Vas15]

V. Vassilevska-Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk). In
10th International Symposium on Parameterized and Exact Computation (IPEC 2015),
volume 43 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17–29.
Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. doi:10.4230/LIPIcs.IPEC.
2015.17.

[Vas18]

V. Vassilevska-Williams. On some fine-grained questions in algorithms and complexity.
In Proceedings of ICM, 2018. To Appear. Available from: http://people.csail.mit.
edu/virgi/eccentri.pdf.

[Wil05]

R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications.
Theoretical Computer Science, 348(2):357–365, 2005. doi:10.1016/j.tcs.2005.09.
023.

16

