%% Theory of Computing
%% File: v017a005.tex
%% Publication date: September 20, 2021
%% Authors: Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
%
%
%
%

%

%

%

%
%

%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

%

\documentclass{toc}

%
%
%
%
%
%
%

\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{hypothesis}[theorem]{Hypothesis}
\theoremstyle{plain}

%
%

\newcommand{\ProblemName}[1]{\textsf{#1}}
\newcommand{\MF}{\ProblemName{Max-Flow}\xspace}
%
\newcommand{\SETH}{SETH\xspace}
\newcommand{\NSETH}{NSETH\xspace}
\newcommand{\APMF}{\ProblemName{All-Pairs Max-Flow}\xspace}
\newcommand{\APR}{\ProblemName{All-Pairs Reachability}\xspace}
%
\newcommand{\TOV}{\ProblemName{$3$OV}\xspace}

\DeclareMathOperator{\SOL}{SOL}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\wdeg}{wdeg}
\DeclareMathOperator{\TTIME}{TIME}
\DeclareMathOperator{\NTIME}{\mathsf{NTIME}}
\DeclareMathOperator{\THALT}{\mathsf{T_{HALT}}}

\newcommand{\MMOD}[1]{\ (\mathrm{mod}\ #1)}

\newcommand\eps{\varepsilon}
%
\newcommand\tO{\ensuremath{\widetilde O}}  %
%
\newcommand{\T}{\mathcal{T}}
\newcommand{\TG}{\mathcal{T}^*}
\DeclareMathOperator{\st}{st}
\DeclareMathOperator{\fn}{fn}
\providecommand{\set}[1]{{\{#1\}}}
\providecommand{\card}[1]{\lvert#1\rvert}
\usepackage{blindtext}
\usepackage[T1]{fontenc}
%
%

%
%
%
\tocdetails{%
  title = {New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs},
%
%
%
%
  number_of_pages = {27},
  number_of_bibitems = {42},
  number_of_figures = {03},
  conference_version = {AKT20}, %
    %
    %
%
%
%
  author = {Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi},
    %
    %
    %
  authorlist = {Amir Abboud, Robert Krauthgamer, Ohad Trabelsi},
    %
    %
    %
    %
    %
    %
    %
%
%
  %
  %
  %
  %
%
  acmclassification = {F.2.2, G.1.6},
    %
    %
  amsclassification = {68W25},
    %
    %
  keywords = {Gomory--Hu tree, conditional lower bounds, max-flow}, %
    %
    %
    %
    %
    %
}   %

    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %

%
%
\tocdetails{%
volume = 17,
number = 5,
year = 2021,
%
%
%
%
%
%
%
received = {December 19, 2019},
revised = {August 29, 2020},
published = {September 20, 2021},
%
%
doi = {10.4086/toc.2021.v017a005},
  %
}   %

\begin{document}

\begin{frontmatter} %

%
%

%
%

\title{New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs\titlefootnote{A conference version of this paper appeared in
the \href{https://doi.org/10.1137/1.9781611975994.4}{Proceedings of the 31st {ACM-SIAM} Symposium on Discrete Algorithms (SODA'20)} \cite{conf-version}.}}

%
%
%
%
%
%
%
%
%
%
%
%


%
%
%
%

%

\author[abboud]{Amir Abboud}
\author[krauthgamer]{Robert Krauthgamer}
\author[trabelsi]{Ohad Trabelsi}

%
%
%
%

%
%
%
%
%
%
\begin{abstract}
We investigate the time-complexity of the \APMF problem:
Given a graph with $n$ nodes and $m$ edges,
compute for all pairs of nodes the maximum-flow value between them.
If \MF (the version with a given source-sink pair $s,t$) can be solved in time
$T(m)$, then $O(n^2) \cdot 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)\cdot T(m)$.
Under the plausible assumption that \MF can be solved in near-linear time
$m^{1+o(1)}$, this half-century old algorithm yields an $nm^{1+o(1)}$ bound.
Several other algorithms have been designed through the years,
including %
${\tO}(mn)$    %
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 \APMF in undirected graphs,
giving an essentially optimal lower bound for the \emph{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)=m^{1+o(1)}$, our algorithm runs in time $m^{3/2 +o(1)}$ and
outputs a cut-equivalent tree (similarly to the Gomory--Hu algorithm).
Even with current \MF algorithms we improve
the %
%
%
state of the art  %
as long as $m=O(n^{5/3-\varepsilon})$.
Finally, we explain the lack of lower bounds by proving a
\emph{non-reducibility} result.
This result is based on a new near-linear time $\tO(m)$
%
%
\emph{nondeterministic}
algorithm for constructing a cut-equivalent
tree and may be of independent interest.
\end{abstract}

\iffalse %
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\tocarxivcategory{cs.DS}

\fi %

\end{frontmatter}

%
%
%

%
\section{Introduction}

In the maximum $st$-flow problem (abbreviated \MF),
the goal is to compute the maximum value of a feasible flow
%
between a given pair of nodes $s,t$ (sometimes called \emph{terminals})
in an input graph.%
\footnote{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~\cite{FF56}.
}
%
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
$\tO(\min\{m^{10/7}U^{1/7},$ $m^{11/8} U^{1/4}, m \sqrt{n}\log U\})$ \cite{Madry16,LS19,lee2014path},
where %
%
%
$\tO(f)$ hides logarithmic factors
and stands for $O(f \log^{O(1)} f)$.
To date, there is no $\Omega(m^{1+\eps})$  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~\cite{ImpaSETH}.%
\footnote{\SETH asserts that for every fixed $\varepsilon>0$
  there is an integer $k\geq 3$,
  such that kSAT on $n$ variables and $m$ clauses
  cannot be solved in time $2^{(1-\varepsilon)n} m^{O(1)}$.
}
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 \MF on \SETH,
  as it would refute the so-called
%
%
Nondeterministic
\SETH (\NSETH)~\cite{carmosino2016nondeterministic}.
We will henceforth assume that \MF can be solved in time $m^{1+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 \APMF),
where the goal is to solve \MF for all pairs of nodes in the graph.
This multi-terminal problem, dating back to 1960 \cite{Mayeda60,Chien60},
is the main focus of our work:
\begin{quotation}
\emph{What is the time complexity of computing \MF between all pairs of nodes?}
\end{quotation}

We will discuss a few natural settings,
\eg, 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(n^2)$ times,
giving a total time bound of $O(n^2)\cdot T(m)$,
which is $n^2 \cdot m^{1+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 \cite{WL93}.


In undirected edge-capacitated graphs,
a seminal paper of Gomory and Hu~\cite{GH61} showed in 1961 how to solve \APMF
using only $n-1$ calls to a \MF algorithm, rather than $O(n^2)$ calls,
yielding an upper bound $O(n) \cdot T(m)$.
(See also~\cite{Gusfield90} 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 \MF,
and under our assumption it would ultimately be $n\cdot m^{1+o(1)}$.
Even more surprisingly, Gomory and Hu showed that all the $n^2$ answers
can be represented using a single tree,
which can be constructed in the same time bound.
Formally,
%
a   %
\emph{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$.%
\footnote{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 \emph{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 \emph{values}
  of the flows (and thus also of the corresponding cuts).
}
See also~\cite{GT01} for an experimental study,
and the Encyclopedia of Algorithms~\cite{Panigrahi16} for more background.
The only algorithm that constructs a cut-equivalent tree
without making $\Omega(n)$ calls to a \MF algorithm
was designed by Bhalgat, Hariharan, Kavitha, and Panigrahi~\cite{BHKP07}.
It runs in time %
${\tO}(mn)$    %
in unit-capacity graphs
(or equivalently, if all edges have the same capacity),
and utilizes a tree-packing approach that was developed in~\cite{Cole03,HKP07},
inspired by classical results of~\cite{Gabow95} and~\cite{Edmonds70}.
However, if \MF can indeed be computed in near-linear time,
then none of the later algorithms beat by a polynomial factor
the time bound $n\cdot m^{1+o(1)}$ of Gomory and Hu's half-century old algorithm.


The time complexity of \APMF becomes higher in settings
where Gomory and Hu's ``tree structure'' \cite{GH61} does not hold.
For instance, in node-capacitated graphs
(where the flow is constrained at intermediate nodes,%
\footnote{Granot and Hassin~\cite{GH86} 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.
}
rather than edges) flow-equivalent trees are impossible,
since there could actually exist $\Omega(n^2)$ different maximum-flow values
in a single graph \cite{HL07} (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~\cite{Mayeda62,Jelinek63,HL07}.
In the last decade, different algorithms were proposed to beat the trivial $O(n^2)\cdot T(m)$ time bound in these harder cases.
The known bound for
%
unit-capacity graphs
is $O(m^\omega)$, due to Cheung, Lau, and Leung~\cite{CLL13},
where $\omega<2.38$ is the matrix multiplication exponent.
A related version, which is obviously no harder than \APMF,
is to ask (among all pairs of nodes) only for flow values that are at most $k$,
assuming unit node-capacities;
for example, the case $k=1$ is the transitive closure problem (reachability).
For $k=2$, an $\tO(n^\omega)$-time algorithm was shown in~\cite{G+17},
and very recently a similar bound was achieved for all $k=O(1)$~\cite{A+18}.
The aforementioned papers~\cite{CLL13,G+17,A+18}
also present improved algorithms for acyclic graphs (DAGs).
In addition, essentially optimal %
${\tO}(n^2)$    %
algorithms were found for \APMF in certain graph families,
including small treewidth \cite{ACZ98},
planar graphs \cite{LNSW12}, and
surface-embedded graphs \cite{BENW16}.


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~\cite{AVY15} proved \SETH-based lower bounds for some multi-terminal variants of \MF,
such as the single-source all-sinks version, but not all-pairs.
Krauthgamer and Trabelsi~\cite{KT18} proved that \APMF cannot be solved
in time $O(n^{3-\eps})$, for any fixed $\eps>0$, unless \SETH is false,
even in the sparse regime $m = n^{1+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(n^2 )\cdot T(m)$ upper bound is optimal if one assumes that $T(m) = m^{1+o(1)}$.
Recently, Abboud et al.~\cite{A+18} proved a conditional lower bound that
is even higher for dense graphs,
showing that an $O(n^{\omega+1-\eps})$-time algorithm
would refute the $4$-Clique conjecture.
However, no non-trivial lower bound is known for undirected graphs.


\subsection{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 \APR in directed graphs
(the aforementioned special case of \APMF with $k=1$).
In BMM the input is two $n\times n$ Boolean matrices $P$ and $Q$,
and the goal is to compute the product matrix $R$ given by
%
\[
  R(a,c) := \bigvee_{b=1}^n \big( P(a,b) \wedge Q(b,c) \big),
  \qquad
  \forall a,c \in [n].
\]
Computing $R$ can be reduced to \APR as follows.
Construct a graph with three layers $A,B,C$ with $n$ nodes each,
where the edges are directed $A \to B \to C$ and represent the two matrices:
$a \in A$ is connected to $b \in B$ iff $P(a,b) =1$;
and $b \in B$ is connected to $c \in C$ iff $Q(b,c)=1$.
It is easy to see that $R(a,c)=1$ iff node $a \in A$ can reach node $c \in C$ (via a two-hop path).

This simple reduction shows an $n^{\omega-o(1)}$ lower bound for \APR
in dense directed graphs assuming the BMM conjecture (see~\cite{AW14}), which states that any combinatorial algorithm (\ie, one that does not use fast matrix multiplication techniques) that solves BMM requires $n^{3-o(1)}$ time.
Higher lower bounds can be proved by more involved reductions
that utilize the extra power of flow over reachability,
\eg, an $n^{3-o(1)}$ lower bound in sparse directed graphs assuming \SETH \cite{KT18}.
Nevertheless, this simple reduction illustrates the main difficulty
in adapting such reductions to undirected graphs.

Consider the same construction but with \emph{undirected edges}
(\ie, 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 \cup C$, the other two layers, have capacity $1$.
Now, consider the maximum flow from $a \in A$ to $c \in C$.
If $R(a,c)=1$ then there is a two-hop path through some $b \in 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 \cup C\setminus\{a,c\}$, whose capacity is only $1$,
hence the maximum flow is bounded by $|A \cup C \setminus \{ a,c \}| = 2n-2$.
This proves the same $n^{\omega-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~\expref{Section}{sec:lower} we utilize this trick in a more elaborate way to prove stronger lower bounds.

\subsection{Our results}

Our main negative result is the first (conditional) lower bound for \APMF that holds in undirected graphs.
For sparse, node-capacitated graphs we are able to match the lower bound $n^{3-o(1)}$ that was previously known only for directed graphs~\cite{KT18},
and it also matches the hypothetical upper bound $n^{3+o(1)}$.

\begin{theorem}
\label{thm1}
Assuming \SETH, no algorithm can solve \APMF in undirected graphs on $n$ nodes and $O(n)$ edges with node capacities in $[n^2]$ in time $O(n^{3-\eps})$
for some fixed $\eps>0$.
\end{theorem}

Our lower bound holds even under assumptions that are weaker than \SETH (see~\expref{Section}{sec:lower}), as we reduce from the $3$-Orthogonal-Vectors (\TOV) problem.
At a high level, it combines the trick described above for overcoming the challenge in undirected graphs, with the previous reduction of \cite{KT18} from \TOV to the directed case.
However, both of these ingredients have their own subtleties and fitting them together requires adapting and tweaking them very carefully.

\medskip

Following our~\expref{Theorem}{thm1}, the largest remaining gap in our understanding of \APMF 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 \cdot m^{1+o(1)}$ for more than half a century, while we cannot even rule out a near-linear $m^{1+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!

\begin{theorem}\label{Theorem:Algorithm}
  There is an algorithm that, given an undirected graph $G$ with $n$ nodes and $m$ edges
%
with unit edge-capacities
and parameter $1\le d \le n$, constructs a cut-equivalent tree in time
%
  ${\tO}( md + \Phi(m,n,d) )$,      %
  where
  \[
    \Phi(m,n,d)=\max\Big\{\sum_{i=1}^{m/d} T(m,n,F_i):\ F_1,\dots,F_{m/d}\geq 0,\sum_{i=1}^{m/d} F_i\leq 2m \Big\}
  \]
  and $T(m,n,F)$ is the time bound for \MF on instances
%
whose
flow value is at most a $F$.
\end{theorem}


Using the current bound on $T(m,n,F)$ we achieve running time
%
  ${\tO}(m^{3/2}n^{1/6})$,       %
and under the plausible hypothesis that $T(m,n)=m^{1+o(1)}$
our time bound becomes $m^{3/2 + o(1)}$.
In the regime of sparse graphs where $m=\tO(n)$ the previous best algorithm of Bhalgat et al.~\cite{BHKP07} had running time
%
  ${\tO}(n^2)$      %
whereas we achieve $\tO(n^{5/3})$, or conditionally $n^{3/2+o(1)}$.
In fact, we improve on their upper bound as long as $m=O(n^{5/3-\eps})$.
Clearly, this also leads to improved bounds for \APMF (with unit edge-capacities), for which the best strategy known is to compute the tree
and then extract the answers in time $O(n^2)$.

\paragraph{Note added in proof.}
Subsequent work further improved the above bound.
First, by employing the recent $\widetilde{O}(m+n^{1.5})$-time \MF algorithm \cite{linearflow21},
our framework immediately gives a better running time $\widetilde{O}(\min\{m^{3/2}n^{1/6},mn^{3/4}+m^{3/2}\})$.
Second, new algorithms were developed for simple graphs:
it has started with~\cite{AKT21_stoc},
and has culminated in running time $n^{2+o(1)}$ \cite{AKT21_arxiv,LPS21},
or a slightly faster $\widetilde{O}(n^2)$ \emph{conditionally} on a linear-time \MF algorithm \cite{Zhang21},
and an even better bound for sufficiently sparse graphs
$\min \{ m^{7/6}n^{1/2+o(1)} , m n^{1/2+o(1)}+m^{1/2}n^{5/4+o(1)} \}$ \cite{LPS21}.

%



\medskip

The main open question remains: Can we prove any super-linear lower bounds for the edge-capacitated case in undirected graphs? Is there an $m^{1+\eps}$ 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.~\cite{carmosino2016nondeterministic}.
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-$2^{n}$-time verifier that a given CNF formula is \emph{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 \MF (using LP duality), showing that a reduction from SAT to these problems would refute \NSETH.

Our final result builds on \expref{Theorem}{Theorem:Algorithm} to design
a near-linear time%
\footnote{We say that a time bound $T(n)$ is near-linear
  if it is bounded by $O(n\log^c n)$ for some constant $c>0$.
}
\emph{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'' (\ie, 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 \emph{certifying algorithm} \cite{certify_survey11,alkassar2011verification} (see \cite{Kunnemann18} for a recent paper with a further discussion of the connections to fine-grained complexity).
Our final non-reducibility result is as follows.

\begin{theorem}
\label{thm3}
If for some $\eps>0$ there is a deterministic fine-grained reduction proving an $\Omega(m^{1+\eps})$ lower bound under \SETH for constructing a cut-equivalent tree of an undirected unit edge-capacitated graph on $m$ edges, then \NSETH is false.
\end{theorem}

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 \cite{carmosino2016nondeterministic,Wil16_MASETH}).
That said, we are not aware of any examples where this barrier has been
%
bypassed with randomization.


\paragraph{Roadmap.} Our main algorithm is described in the \expref{Section}{GHU_Alg}. The nondeterministic algorithm and non-reducibility result are presented in \expref{Section}{sec:nondet}. We then present our lower bounds in \expref{Section}{sec:lower}. The last section discusses open questions.


\section{Algorithm for a cut-equivalent tree}
\label{GHU_Alg}

The basic strategy in our algorithm for unit edge-capacities
is to handle separately nodes whose connectivity (to other nodes)
is high from those whose connectivity is low.
The motivation comes from the simple 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~\cite{HKP07,BHKP07}),
to compute the parts of the tree that correspond to small connectivities,
and the second stage uses another method
(the classical Gomory--Hu   %
algorithm~\cite{GH61})
to complete it to a cut-equivalent tree (see~\expref{Figure}{Figs:GH_trees_3}).
Let us briefly review these two methods.


\paragraph{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 \emph{super-node},
which means that it is associated with a subset $V_i\subseteq V$;
and these super-nodes form a partition $V=V_1 \sqcup\cdots\sqcup V_l$.
At each iteration, the algorithm picks arbitrarily two graph nodes $s,t$
that lie in the same tree super-node $i$, \ie, $s,t\in V_i$.
The algorithm then constructs from $G$ an auxiliary graph $G'$
by merging nodes that lie in the same connected component of  $\T\setminus\set{i}$
and invokes a \MF algorithm to compute in this $G'$ a minimum $st$-cut, denoted $C'$.
(For example, if the current tree is a path on super-nodes $1,\ldots,l$,
then $G'$ is obtained from $G$ by merging $V_1\cup\cdots\cup V_{i-1}$
into one node and $V_{i+1}\cup\cdots\cup V_l$ 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 $V_i=S\sqcup T$ with $s\in S$ and $t\in 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 $C'$,
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 $C'$
(more precisely,
%
a neighbor
$j$ is connected to the side containing $V_j$).

\begin{figure}[ht]
  \centering
    \includegraphics[width=6.2in]{GH_trees_3}
    \caption{An illustration of the construction of $\T$.  Left: $\T$ right before the partition of the super-node $V_i$. Middle: after the partitioning of
%
$V_i$.
Right: $\T$ as it unfolds after the Gomory--Hu algorithm finishes.}
    \label{Figs:GH_trees_3}
\end{figure}

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 \cite{GH61} that for every $s,t\in 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\neq t\in V_i$.


\paragraph{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 using the Gomory--Hu algorithm,
but as stated below (in \expref{Lemma}{Lemma:Partial}),
faster algorithms were designed in~\cite{HKP07,BHKP07},
see also~\cite[Theorem $3$]{Panigrahi16}.
We show below (in \expref{Lemma}{lem:truncatedGH}) 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.


\begin{definition}[$k$-Partial Tree~\cite{HKP07}]
  A \emph{$k$-partial tree} of a graph $G=(V,E)$ is a weighted tree on $l\leq \card{V}$ super-nodes constituting a partition $V=V_1 \sqcup\cdots\sqcup V_l$, with the following property:
  For every two nodes $s,t\in V$ whose minimum-cut value in $G$ is at most $k$, $s$ and $t$ lie in different super-nodes $s\in S$ and $t\in 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.
\end{definition}

\begin{lemma}[\cite{BHKP07}]
\label{Lemma:Partial}
There is an algorithm that given an undirected graph with $n$ nodes and $m$ edges with unit edge-capacities and an integer $k\in [n]$, constructs a $k$-partial tree in time $\tO(mk)$.
\end{lemma}

\begin{lemma} \label{lem:truncatedGH}
  Given a $k$-partial tree $T_{\mathrm{low}}$ of a graph $G=(V,E)$, there is a truncated execution of the Gomory--Hu algorithm that produces $T_{\mathrm{low}}$ (\ie, its auxiliary tree $\T$ becomes $T_{\mathrm{low}}$).
\end{lemma}

\begin{proof}
  Consider an execution of the Gomory--Hu algorithm with the following choices.
  At each iteration, pick any two nodes $s,t\in V$
  that lie in the same super-node $i$ of the current tree $\T$
  (hence they are feasible choice in a Gomory--Hu execution)
  \emph{but furthermore} lie in different super-nodes of $T_{\mathrm{low}}$,
  as long as such $s,t$ exist.
  Then split super-node $i$ of $\T$ using the minimum $st$-cut induced by $T_{\mathrm{low}}$ (rather than an arbitrary minimum $st$-cut).
  As this cut corresponds to an edge in $T_{\mathrm{low}}$,
  it cannot split any super-node of $T_{\mathrm{low}}$,
  which implies, by an inductive argument,
  that the super-nodes of $T_{\mathrm{low}}$ 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 $T_{\mathrm{low}}$, 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 $A'\subseteq A, B'\subseteq B$ of super-nodes of $T_{\mathrm{low}}$ with an edge of capacity $c$
%
between
$A'$ and $B'$ in $T_{\mathrm{low}}$.
  Notice also that a pair $s,t$ as required above can be chosen
  as long as $\T$ is not equal to $T_{\mathrm{low}}$, and hence, together with the two inductive claims above,
  the Gomory--Hu execution continues until $\T$ becomes exactly $T_{\mathrm{low}}$.
\end{proof}


\medskip
We are now ready to prove our main theorem.

\begin{proof}[Proof of \expref{Theorem}{Theorem:Algorithm}]
Let $G=(V,E)$ be an input undirected graph with unit edge-capacities,
and denote by $V_{\mathrm{low}}$ all the nodes in $G$ whose degrees are at most
the chosen parameter $d\in [n]$,
and by $V_{\mathrm{high}}=V\setminus V_{\mathrm{low}}$ the nodes whose degrees are greater than $d$.

First use \expref{Lemma}{Lemma:Partial} to construct a $d$-partial tree $T_{\mathrm{low}}$,
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 $V_{\mathrm{low}}$ is in a singleton super-node of $T_{\mathrm{low}}$, since its minimum cut value to any other node is at most $d$; thus a super-node $V_i$ in $T_{\mathrm{low}}$ has more than one node if and only if it contains only nodes in $V_{\mathrm{high}}$.
Moreover, by the properties of $T_{\mathrm{low}}$, two nodes have minimum-cut value greater than $d$ if and only if they are in the same super-node $V_i$.
Since by \expref{Lemma}{lem:truncatedGH} there exists a truncated Gomory--Hu execution that produces $T_{\mathrm{low}}$, a Gomory--Hu execution starting with $T_{\mathrm{low}}$ 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 $T_{\mathrm{low}}$ takes $\tO( m d )$ time,
and the second step of the Gomory--Hu execution
takes $\card{V_{\mathrm{high}}}$ invocations of \MF, that is running time $\sum_{i=1}^{m/d}T(m,n,F_i)$.
Finally, we will use the following known claim regarding a bound on the total sum of capacities of cut-equivalent trees.
\begin{claim}[From Lemma $4$ in \cite{BHKP07}]\label{tree_bound}
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$.
\end{claim}
Now, since every invocation of maximum $st$-flow with value $F_i$ in our algorithm determines a unique edge with capacity $F_i$ in the final cut-equivalent tree, and by~\expref{Claim}{tree_bound} the sum of the capacities over all the edges of the cut-equivalent tree satisfies
$\sum_{i=1}^{m/d} F_i\leq 2m$,
it holds that the total time spent on the $m/d$ invocations of \MF is bounded by $\Phi(m,n,d)$.
Thus, the proof of \expref{Theorem}{Theorem:Algorithm} is concluded.
\end{proof}

We use the $T(m,n,F)=\tO(m+m^{3/4}n^{1/4}F^{1/2})$ time algorithm by~\cite{SidfordT18} to optimize our running time.
By the concavity of $F^{1/2}$, the maximum of $\sum_{i=1}^{m/d}T(m,n,F_i)$ is attained when all $F_i=d$.
By setting $d=\sqrt{m}n^{1/6}$ we get
\[
  \sum_{i=1}^{\sqrt{m}/n^{1/6}} (m+m^{3/4}n^{1/4}m^{1/4}n^{1/12})=
\sum_{i=1}^{\sqrt{m}/n^{1/6}} m n^{1/3}=
m^{3/2}n^{1/6}\,,
\]
which is faster than the known $\tO(mn)$-time algorithm of~\cite{BHKP07} whenever $m\in [n,n^{5/3}]$.

Finally, relying on a hypothetical $m^{1+o(1)}$-time algorithm for \MF,
we could set $d=\sqrt{m}$ to get a total running time of $m^{1+o(1)}\cdot m/\sqrt{m}+\tO(m\cdot \sqrt{m})\leq m^{3/2+o(1)}$, as claimed immediately after \expref{Theorem}{Theorem:Algorithm}.



\section{Near-linear nondeterministic algorithm for cut-equivalent tree}\label{sec:nondet}

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 $n^{1+\delta-o(1)}$, for a fixed $\delta>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 \expref{Theorem}{thm3}.


Our main technical result in this section (\expref{Theorem}{nondet:main})
is a fast \emph{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~\cite{carmosino2016nondeterministic},
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 \expref{Section}{subsec:reduction}).

Generally speaking, a search problem $P$ is a binary relation,
and we say that $S$ is a solution to instance $x$ iff $(x,S)\in P$.
Let $\SOL(x)=\set{S: (x,S)\in P}$ denote the set of solutions for instance $x$.
We say that $P$ is a \emph{total search problem}%
\footnote{In some of the previous literature it is called a
\textit{total function}, although it is actually a relation rather than a function.}
if every instance $x$ has at least one solution, \ie, $\SOL(x)\neq \emptyset$.
Let $\bot$ be the ``don't know'' symbol and assume that $\bot \notin \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$.

\begin{definition}[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 $\card{x}=n$:
\begin{enumerate}
\item \label{it:time}
  $\forall g, \THALT(M(x,g))\leq T(n)$,
  \ie, the time complexity of $M$ on input $x$ with guess $g$ is bounded by $T(n)$;
\item \label{it:a}
  $\exists g, M(x,g)\in \SOL(x)$, \ie, at least one guess leads $M$ to output a solution;
\item \label{it:b}
  $\forall g, M(x,g) \in \{\bot\}\cup \SOL(X)$, \ie, every guess leads $M$ to output either a solution or ``don't know.''
\end{enumerate}
Note that the time bound in~\expref{item}{it:time} does not depend on $g$, which is useful for our purpose.
\end{definition}

We can now state the main technical result of this section.
We prove it in \expref{Section}{sec:nondet_main},
and then use it in \expref{Section}{subsec:reduction} to prove \expref{Theorem}{thm3}.

\begin{theorem}\label{nondet:main}
The nondeterministic complexity of constructing a cut-equivalent tree
  for an input graph with unit edge-capacities is $\tO(m)$,
  where $m$ is the number edges in the graph.
\end{theorem}

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~\cite{AnariV18}
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 $\tO(m)$.
Towards overcoming this challenge, we show a basic structural result about cut-equivalent trees (see~\expref{Claim}{claim:technical} 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 \MF could be computed in linear time, since a \MF 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.

\subsection{The nondeterministic algorithm}
\label{sec:nondet_main}

We now prove \expref{Theorem}{nondet:main}.
Let $G=(V,E)$ be the input graph, and let $n=\card{V}$ and $m=\card{E}$.

\paragraph{Overview.}
At a high level, the nondeterministic algorithm
first guesses nondeterministically a cut-equivalent tree $\TG$,
and then verifies it by a (nondeterministic) process that resembles
an execution of the Gomory--Hu algorithm that produces $\TG$.
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 \expref{Section}{GHU_Alg},
that every tree node $i$ is associated with $V_i\subseteq V$,
and these super-nodes form a partition $V=V_1 \sqcup\cdots\sqcup V_l$.
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 \emph{intermediate tree}.
If all guesses work well, then eventually every super-node is a singleton
and the tree $\T$ corresponds to $\TG$.
Otherwise (some step in the verification fails), the algorithm outputs $\bot$.

In a true Gomory--Hu execution, every iteration partitions some super-node
into exactly two super-nodes connected by an edge (say $V_i=S\sqcup 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 $V_i=\set{w}\sqcup V_{i,1}\sqcup\dots\sqcup V_{i,d}$,
where super-node $\set{w}$ has edges to all super-nodes $V_{i,1},\ldots,V_{i,d}$).
We call this an \emph{expansion step} (see~\expref{Figure}{Figs:Expansion}),
and the node in the center of the star (\ie, $w$) the \emph{expanded node}.
These expansion steps will be determined from the guess $\TG$.
For example, in the extreme case that $\TG$ itself is a star,
our verification process will take only one expansion step
instead of $\card{V}-1$ Gomory--Hu steps.

\begin{figure}[ht]
  \centering
    \includegraphics[width=6.2in]{Expansion}
    \caption{An illustration of the verification of a guessed tree $\TG$. Left: the intermediate tree $\T$ right before an expansion step of the node $c_j$ in the super-node $V(\TG_{c_j})$. Middle: after the expansion step (of $c_j$, in the dashed circle) where $U_1,...,U_4$ are $c_j$'s neighbors in $\T^{(j+1)}$ such that $\bigcup_{i=1}^4 U_i\cup \set{c_j}=V(\TG_{c_j})$. Right: the guessed cut-equivalent tree $\TG$.}
    \label{Figs:Expansion}
\end{figure}

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 $G'$,
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 $\tO(m)$,
because in some scenarios (\eg, in the above example where $\TG$ is a star),
most of the $\card{V}-1$ minimum-cut computations are performed
on an auxiliary graph $G'$ of size that is comparable to $G$, \ie, $\Omega(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 \emph{linear} in the size of $G'$.
Second, we design a specific sequence of expansion steps
such that the total size of \emph{all auxiliary graphs $G'$} is $\tO(m)$.

\paragraph{Detailed algorithm.}

The algorithm first guesses nondeterministically an edge-capacitated tree $\TG$,
and then verifies, as explained below, that it is a cut-equivalent tree.
Here, verification means that upon the failure of any step,
\eg, verifying some equality (say between the cut and flow values),
the algorithm terminates with output $\bot$.
(By the same reasoning, we may assume that all guesses are proper,
\eg, a guessed tree is indeed a tree.)
%
The verification process starts by picking
a sequence of nodes $c_0,c_1,c_2,\ldots$ using the guess $\TG$,
as follows.
Recall that a \emph{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 \emph{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 $\TG$,
which takes time $O(n\log n)$.
For each recursion depth $i\ge 0$ (where clearly $i\le \log n$),
denote the set of centroids computed at depth $i$ by $D_i\subset V$.
For example, $D_0$ contains exactly one centroid, of the entire $\TG$.
Now let $c_0,c_1,c_2,\ldots$ be the centroids in this decomposition
in order of increasing depth, \ie, starting with the one centroid $c_0\in D_0$,
followed by the centroids from $D_1$ (ordered arbitrarily), and so forth.
Let $\TG_{c_j}$ be the subtree of $\TG$ in which the centroid $c_j$ was computed; for example $\TG_{c_0}=\TG$.
\begin{observation}\label{observation:disjoint}
For every two centroids from the same depth,
$c_j\neq c_{j'}\in D_i$,
the corresponding subtrees $\TG_{c_j}$ and $\TG_{c_{j'}}$ are node disjoint.
\end{observation}

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 $c_0,c_1,c_2,\ldots$
(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 $\TG_{c_j}$,
therefore it defines a partition
$V(\TG_{c_j}) = \set{c_j}\sqcup U_1 \sqcup\dots\sqcup U_d$,
where $U_1,\ldots,U_d$ are the connected components after removing $c_j$.
Notice that $d = \deg_{\TG_{c_j}}(c_j)\leq \deg_{\TG}(c_j)$,
and that each $U_k$, $k\in [d]$, contains exactly one node $u_k\in U_k$
that is a neighbor of $c_j$ in $\TG_{c_j}$.
The expansion step replaces the super-node $V(\TG_{c_j})$ in $\T$
with $d+1$ super-nodes $\set{c_j},U_1,\dots,U_d$.
(We slightly abuse notation and use a subset of nodes like $V(\TG_{c_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 $\set{c_j}$ at the center
and each newly-added edge $(\set{c_j}, U_k)$
is set to the same capacity as the edge $(c_j, u_k)$ in the guess $\TG$.
In addition, every edge that was incident to super-node $V(\TG_{c_j})$,
say $(V(\TG_{c_j}),W)$, is modified to an edge $(U,W)$,
where $U$ is one of the new super-nodes $\set{c_j},U_1,\dots,U_d$,
chosen according to the edge in $\TG$ that was used to set
a capacity for $(V(\TG_{c_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 $\TG$,
\ie, the induced subgraph $\TG[U]$ is connected.
Moreover, eventually every super-node will be a singleton,
and the intermediate tree will exactly match the guess $\TG$.
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 $G'_j$
just as in the Gomory--Hu algorithm (see \expref{Section}{GHU_Alg}).
Specifically, $G'_j$ is constructed by taking $G$,
and then for each connected component of $\T^{(j)}\setminus \set{V(\TG_{c_j})}$
(\ie, after removing super-node $V(\TG_{c_j})$ from $\T^{(j)}$),
merging the nodes in (all the super-nodes in) this component into a single node.
%
Our analysis shows (in~\expref{Claim}{claim:GH})
that for all $s,t\in V(\TG_{c_j})$,
every minimum $st$-cut in the auxiliary graph $G'_j$
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 (\expref{Lemma}{lemma:construction_time}).


Observe that each neighbor $u_k$ of $c_j$ in $\TG_{c_j}$
defines a $(c_j,u_k)$-cut in the auxiliary graph $G'_j$,
given by the two connected components of $\TG\setminus \set{(c_j,u_k)}$.
The algorithm evaluates for each $u_k$ the capacity of this cut in $G'_j$,
and verifies that it is equal to the capacity of the newly-added edge $(\set{c_j}, U_k)$ (set to be the same as of edge $(c_j, u_k)$ in $\TG$).
In fact, all these cuts evaluations are performed not sequentially
but rather simultaneously for all $k\in [d]$, as follows.
The key observation is that if we denote
each aforementioned $(c_j,u_k)$-cut by $(V(G'_j)\setminus C'_k, C'_k)$,
where $u_k\in C'_k$,
then $\set{c_j},C'_1,\ldots,C'_d$ are disjoint subsets of $V(G'_j)$.
One can clearly evaluate the capacity of all these $d$ cuts
in a single pass over the edges of $G'_j$,
and since each edge contributes to at most two cuts (by the disjointness),
this entire pass takes only linear time $O(\card{E(G'_j)})$.

Next, to verify that each $(c_j,u_k)$-cut exhibited above,
namely, each $(V(G'_j)\setminus C'_k, C'_k)$,
is actually a minimum $(c_j,u_k)$-cut in $G'_j$,
the algorithm finds a flow whose value is equal to the cut capacity.
In order to perform this task simultaneously for all $k\in[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 \emph{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, $\MF_{G}(s,t)$ is the maximum $st$-flow value in a graph $G$.


\begin{lemma}\label{lemma:packing}
Given an undirected multigraph $H=(V_H,E_H)$, a root node $r\in V_H$, and a function $\lambda:V_H\rightarrow [\card{E_H}]$, it is possible to nondeterministically verify in time $\tO(\card{E_H})$ that
\begin{equation}\label{eq}
  \forall v\in V_H\setminus\set{r},
  \qquad
  \MF_{H}(r,v)\geq \lambda(v).
\end{equation}
Here, nondeterministic verification means that
if~\eqref{eq} holds then there exists a guess that leads to output ``yes'';
and if~\eqref{eq} does not hold then every guess leads to output ``no.''
\end{lemma}

\begin{proof}
We use the following theorem known from~\cite[Theorem $2.7$]{Bang-Jensen95},
in its variation from~\cite{Cole03} as the Tree Packing Theorem.

\begin{theorem}\label{theorem:BHKP}
Let $H_e$ be an Eulerian directed graph, and $r_e$ be a node in $H_e$.
Then there exist $\max_{v\neq r_e}\{\MF_{H_e}(r_e,v)\}$ edge-disjoint directed trees rooted at $r_e$, such that each node $v\in H_e$ appears in exactly $\MF_{H_e}(r_e,v)$ trees.
\end{theorem}

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 directions%
\footnote{The subdivision and orientation are used to transform
  the undirected multigraph to a directed graph.
}
to obtain an Eulerian directed graph $H_e$.
Observe that the minimum-cut values between pairs of original nodes in $H_e$ are the same as in $H$.
%
Now find all maximum-flow lower-bound values from $r$
in $H_e$ by guessing $\card{V_H}$ edge-disjoint trees and then counting occurrences of each node in those trees. By \expref{Theorem}{theorem:BHKP}, these counts correspond to maximum-flow lower-bound values from $r$. And so if the guessed trees support the values given by $\lambda$, 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.
\end{proof}


The verification algorithm then applies \expref{Lemma}{lemma:packing}
to $G'_j$ with $c_j$ as the root, and verifies in time $\tO(\card{E(G'_j)})$
that the maximum-flow from $c_j$ to each $u_k$
is at least the capacity of the $(c_j,u_k)$-cut exhibited above
(in turn verified to be equal to the capacity of edge $(c_j, u_k)$ in $\TG$).


\paragraph{Correctness.}

We begin by claiming that if the guessed tree $\TG$ is a correct cut-equivalent tree of $G$, then our algorithm outputs $\TG$; we discuss the complement case afterwards.
Since $\TG$ is a cut-equivalent tree, every verification step of an expansion will not fail and so the algorithm will not terminate prematurely, and output $\TG$, as required.

Next, we show that if $\TG$ 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.

\begin{claim}\label{claim:GH}
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.
\end{claim}

\begin{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 $U_{1},...,U_{d}$ are $\set{c_j}$'s neighbors in $\T^{(j+1)}$ such that $\bigcup_{i=1}^d U_i\cup \set{c_j} = V(\TG_{c_j})$,
and $u_{1},...,u_{d}$ are the nodes by which the capacities of the edges $(\set{c_j},U_k)$, $k\in [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,u_{k}$ from the super-node containing it in $\T$ as the pair $s,t$ in the Gomory--Hu algorithm description (see the description in \expref{Section}{GHU_Alg}), 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,u_{k}$ as in $\TG$ (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 (\ie, verified correctly), thus all the cuts chosen for the partitioning are minimum-cuts.
\end{proof}

Now, assume for the contrary that $\TG$ is not a cut-equivalent tree of $G$ and our algorithm still produces it.
As a consequence of~\expref{Claim}{claim:GH}, there is a sequence of Gomory--Hu steps attaining $\TG$, contradicting the proof of correctness of the Gomory--Hu algorithm (which cannot produce $\TG$).
Thus, it is impossible that our algorithm finishes and produces $\TG$, and so in one of the minimum-cut verifications after an expansion step, the cut witness inspired from $\TG$ 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.

\paragraph{Running time.}
Observe that the running time of a single expansion step,
\ie, 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 \expref{Lemma}{lemma:size} 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~\expref{Corollary}{cor:total}
that the total size of all auxiliary graphs over all depths is $\tO(m)$.

\begin{lemma}\label{lemma:size}
Let $D_q=\{c_{j_1},\dots,c_{j_2}\}$ contain the centroids at depth $q$.
Then the total size of $G'_{j_1},\dots,G'_{j_2}$ is at most $O(m)$.
\end{lemma}

\begin{corollary}\label{cor:total}
The total size of all auxiliary graphs
(over all depths) is $\tO(m)$.
\end{corollary}

\begin{proof}[Proof of \expref{Lemma}{lemma:size}]
Let us count for each edge $uv\in E(G)$ in how many auxiliary graphs
of depth $q$ it appears.
This quantity turns out to be at most $2+(\dist_{\T}(u,v)-1)$,
where $\dist_{\T}(u,v)$ is the hop-distance,
\ie, 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({\T_{c_j}})$ for some auxiliary graph $G'_j$.
Clearly, every such edge is in at most two auxiliary graphs at depth $q$,
because there is at most one index $j'\in D_q$ where $u\in V({\T_{c_{j'}}})$
and at most one index $j''\in D_q$ where $v\in V({\T_{c_{j''}}})$.
The summand $\dist_{\T}(u,v)-1$ bounds the other appearances of edge $uv$,
\ie, when neither $u$ nor $v$ belongs to some $V({\T_{c_j}})$,
and is proved in the claim below.
While our graph has unit capacities, the claim holds for general capacities.

\begin{claim}\label{claim:technical}
For every cut-equivalent tree $\T$ of a graph $G$ with edge capacities $c_G:E\rightarrow \mathbb{R}_+$,
$$
\sum_{uv\in E(G)} c_G(u,v)\cdot\dist_{\T}(u,v)\leq 2\sum_{uv\in E(G)} c_G(u,v).
$$
\end{claim}

\begin{proof}
  We first show that $\sum_{uv\in E_{G}} c_G(u,v)\cdot\dist_{\T}(u,v) = \sum_{e\in E_{\T}} c_{\T}(e)$,
  where $c_{\T}(\cdot)$ denotes edge capacity in $\T$.
  Recalling that $\T$ is a cut-equivalent tree,
  each $c_{\T}(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\in E(G)$
  and counting for each edge in how many such cuts it appears.
  Moreover, the count for each graph edge $uv\in E(G)$
  is exactly $\dist_{\T}(u,v)$ contributions of $c_G(u,v)$,
  giving altogether the left-hand side.

  Second, we show that $\sum_{uv\in E(\T)} c_{\T}(u,v)\leq 2\sum_{uv\in E(G)} c_G(u,v)$ (see also Lemma $4$ in~\cite{BHKP07}).
  To see this, observe that $c_{\T}(u,v)\leq \min\{\deg_{c_G}(u), \deg_{c_G}(v)\}$
  where $\deg_{c_G}(u)$ is the total capacity of edges incident to $u$.
  Now fix a root vertex in $\T$,
  and bound each tree edge by $c_{\T}(u,v)\leq \deg_{c_G}(v)$,
  where $v$ is the child of $u$ (\ie, 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.
\end{proof}

To complete the proof of \expref{Lemma}{lemma:size},
recall that by~\expref{Observation}{observation:disjoint} the super-nodes $V(\T_{c_{j_1}}),\ldots,$ $V(\T_{c_{j_2}})$ of the same depth $q$ are pairwise disjoint. Thus, an edge $uv$ appears in at most $dist_{\TG}(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~\expref{Claim}{claim:technical}.
This concludes \expref{Lemma}{lemma:size}.
\end{proof}

Next, we bound the time it takes to construct all the auxiliary graphs.
\begin{lemma}\label{lemma:construction_time}
The total time it takes to construct the auxiliary graphs for all the expansions in the centroid decomposition is $\tO(m)$.
\end{lemma}

\begin{proof}
Let $c_j$ be a node that is expanded at some depth $q\geq 1$, and let $c_{j,1},\dots,c_{j,d}$ be the expanded nodes in $U_{1},\dots,U_{d}$, respectively at depth $q+1$ (or just $\bot$ for singletons).

Note that $G'_{j,1},\dots,G'_{j,d}$ (whichever exist) can all be constructed in total time that is linear in the size of $G'_j$.

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$ (\ie, the entire graph) can trivially be constructed in $O(m)$ time and is linear in the input size, it follows by~\expref{Corollary}{cor:total} that the total construction time of the auxiliary graphs for all depths takes at most $\tO(m)$ time.
\end{proof}

\subsection{Reduction from a decision problem to a total search problem}\label{subsec:reduction}

Let us start with the formal statement of \NSETH.
\begin{hypothesis}[Nondeterministic Strong Exponential-Time Hypothesis (\NSETH)]
For every $\varepsilon>0$ there exists $k=k(\varepsilon)$ such that $k$-TAUT (the language of all $k$-DNF formulas that are tautologies) is not in $\NTIME(2^{n(1-\varepsilon)})$.
\end{hypothesis}
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.

\begin{definition}[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 $T_L(\cdot)$ and $T_P(\cdot)$ be time bounds. We say that $(L,T_L)$ admits a fine-grained reduction to $(P,T_P)$ if for all $\eps>0$ there is a $\gamma>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:

\begin{enumerate}
\item \label{itit:a}
	$M^P$ decides $L$ correctly on all inputs when given a correct oracle for $P$.
\item \label{itit:b}
  Let %
$\widetilde{Q}(M^P,x)$    %
denote the set of oracle queries made by $M^P$ on input $x$ of length $n$. Then the query lengths obey the bound
%
$$
\forall x, \qquad
\THALT(M^P,\card{x}) + \sum_{q\in \widetilde{Q}(M,x)}(T_P(\card{q}))^{1-\varepsilon}
\leq(T_L(n))^{1-\gamma},
$$
where $\THALT(M^P,\card{x})$ is the maximal time $M^P$ runs on  inputs of size $\card{x}$.
\end{enumerate}
\end{definition}
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.~\cite{carmosino2016nondeterministic}.

\begin{theorem}\label{nondet:if}
Suppose $P$ is a total search problem with nondeterministic time complexity $T(m)$.
If for some $\delta>0$ there is a deterministic fine-grained reduction from $k$-SAT with time-bound $2^n$ to $P$ with time bound $T(m)^{1+\delta}$, \ie, from $(k\text{-SAT},2^n)$ to $(P,T(m)^{1+\delta})$, then \NSETH is false.
\end{theorem}

\begin{proof}
We will use the assumption of the theorem to describe a nondeterministic algorithm for $k$-TAUT that refutes \NSETH.
Let $\phi$ be an instance of $k$-TAUT, and note that $\phi \in k$-TAUT iff $\neg \phi \notin k$-SAT.
Our nondeterministic algorithm $A$ first computes the CNF formula $\neg \phi$, then simulates the assumed reduction $M_1$ from $k$-SAT to $P$ on $\neg \phi$, and eventually outputs the negation of the simulation's answer, or \textsl{Reject} if the simulation returns $\bot$.

Let $M_2$ be the Turing Machine showing that $P$ has nondeterministic time complexity $T(m)$.
Whenever the reduction $M_1$ produces a query to $P$, our algorithm $A$ executes $M_2$ on this query with some guess string $g$. Let $g_i$ be the guess string used for the $i^{th}$ query to $P$ made by $M_1$. If any of the executions of $M_2$ throughout the simulation outputs $\bot$, then $A$ stops and outputs \textsl{Reject}. Otherwise (all executions output valid answers), the simulation continues until $M_1$ terminates. At this point, the output of $M_1$ must be correct, and our algorithm $A$ outputs the opposite answer.

Let us argue about the correctness of our algorithm. First, it only outputs \textsl{Accept} if the guesses and all answers to the $P$-queries were correct and then $M_1$ rejected, meaning that $\neg \phi \notin k$-SAT \ie, $\phi \in k$-TAUT.
Second, for every yes-instance $\phi \in k$-TAUT there is at least one sequence of guesses $g_1,g_2,\ldots$ that makes $A$ output \textsl{Accept}, due to the correctness of the reduction $M_1$ and the fact that $M_2$ nondeterministically computes $P$ correctly.
Finally, the running time of $A$ can be upper bounded by
%
$$
\THALT(M_1) + \sum_{q\in \widetilde{Q}(M_1,x)}T(\card{q}) \leq \THALT(M_1)
+\sum_{q\in \widetilde{Q}(M_1,x)}T(\card{q})^{(1+\delta)(1-\eps)}\leq (2^n)^{1-\gamma}
$$
for $0<\varepsilon<\delta$ where the last inequality is due to the reduction from $k$-SAT to $P$, $\THALT(M_1)$ is the time of operations done by $M_1$,
%
$\widetilde{Q}(M_1,x)$
is the queries made by $M_1$ to the $P$-oracle on an input $x$, and the last inequality follows for some $\gamma(\varepsilon)>0$ because $M_1$ is a correct fine-grained reduction.
Thus, $A$ refutes \NSETH.
\end{proof}

Since the construction of a cut-equivalent tree is a total search problem, and by \expref{Theorem}{Theorem:Algorithm} its nondeterministic complexity is $\tO(m)$, applying \expref{Theorem}{nondet:if} implies that any deterministic reduction from \SETH to the construction of a cut-equivalent tree that implies a lower bound of $\Omega(m^{1+\delta})$, for some $\delta>0$, would refute \NSETH, concluding \expref{Theorem}{thm3}.

\section{Conditional lower bound for \APMF}\label{sec:lower}

In this section we prove a conditional lower bound for \APMF
in undirected graphs with node capacities.
Our construction is inspired by the one in~\cite{KT18}, 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~\cite{KT18} 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 \TOV problem.
\begin{definition}[\TOV]
Given three sets $U_1, U_2, U_3 \subseteq \{0,1\}^d$ containing $n$ binary vectors each, over dimension $d$, decide if there is a triple $(\alpha,\beta,\gamma)$ of vectors in $U_1 \times U_2 \times U_3$, whose dot product is $0$. That is, a triple for which for all $i \in [d]$ at least one of $\alpha[i],\beta[i],\gamma[i]$ is equal to $0$.
\end{definition}

An adaptation of the reduction by Williams \cite{Wil05} shows that  \TOV cannot be solved in $O(n^{3-\eps})$ time for any $\eps>0$ and $d=\omega(\log{n})$, unless \SETH is false (see \cite{ABV15}).
For us, it suffices to assume the milder conjecture that \TOV cannot be solved in  $O(n^{3-\eps})$ time when $d=n^{\delta}$, for all $\eps,\delta>0$.
Refuting this conjecture
%
would have    %
important implications beyond refuting \SETH \cite{GIKW17,ABDN18}, \eg, it
%
would refute  %
the Weighted Clique Conjecture.

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.


\begin{lemma}\label{ProofsCapLemma}
\TOV over vector sets of size $n$ and dimension $d$ can be reduced to \APMF in undirected graphs with $\Theta(n\cdot d)$ nodes, $\Theta(n\cdot d)$ edges, and node capacities in $[2n^2d]$.
\end{lemma}
Since, as explained earlier, the \TOV conjecture is a consequence of \SETH,
%
\expref{Theorem}{thm1} immediately follows from \expref{Lemma}{ProofsCapLemma}, which is proved below.

\begin{proof}[Proof of \expref{Lemma}{ProofsCapLemma}]
Given a \TOV 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.    %

\paragraph{An intermediate construction with few directed edges.}
To simplify the exposition, we start with a construction of a graph $G'$ in which most of the edges are undirected, but some are still directed (see~\expref{Figure}{Figs:REDUCTION_CAP}).
\begin{figure}[ht]
  \centering
    \includegraphics[width=5.2in]{REDUCTION}
%
  \caption{An illustration of part of the reduction. Here, $U_1$, $U_2$, and $U_3$ have two vectors each; $\alpha$ and $\widetilde{\alpha}$ in $U_1$, $\beta$ and $\widetilde{\beta}$ in $U_2$, $\gamma$ and $\widetilde{\gamma}$ in $U_3$. Bolder nodes correspond to nodes of higher capacity, and dashed edges are conditional on the input instance. For simplicity, we omit the edges not relevant to $\alpha$ and $\widetilde{\gamma}$, and also the edges from nodes in $\{C_i^0\}_{i\in[3]}$ to nodes in $\{\beta',\widetilde{\beta}'\}$. In this illustration, $\alpha=110$, $\beta=101$, $\widetilde{\beta}=001$, and $\widetilde{\gamma}=101$. Note that the triple $\alpha$, $\widetilde{\beta}$, and $\widetilde{\gamma}$ has an inner product $0$, and indeed the maximum flow from $\alpha$ to $\widetilde{\gamma}$ is $2\cdot 3 -1=5$.}
    \label{Figs:REDUCTION_CAP}
\end{figure}

Our final graph $G$ will be very similar to $G'$. 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 $G'$ on $N$ nodes $V_1\cup V_2\cup V_3\cup A\cup B\cup \{v_B\}$.
The layer $V_1$ contains a node $\alpha$ of capacity $1$ for every vector $\alpha\in U_1$.
$V_2$ contains $d+1$ nodes for every vector $\beta\in U_2$: $d$ nodes of capacity $1$ denoted by $\beta_i$ for every $i\in[d]$, plus a node denoted by $\beta'$ of capacity $d-1$.
$V_3$ contains a node $\gamma$ of capacity $1$ for every vector $\gamma$ in $U_3$.
The intermediate layer $A$ contains $2d$ nodes: two nodes $C_i^{0}$ and $C_i^{1}$ of capacity $n$ for every coordinate $i\in [d]$.
The other intermediate layer $B$ contains a node $C_i$ of capacity $n$ for every coordinate $i\in [d]$.
Finally, the auxiliary node $v_B$ has capacity $n(d-1)$.
With a slight abuse of notation, we will use the following symbols in the following ways: $\alpha$ will be either a node in $V_1$ or a vector in $U_1$; $\beta$ will be a vector in $U_2$;  $\gamma$ will be either a node in $V_3$ or a vector in $U_3$; and $C_i$ 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 \TOV instance.
\begin{itemize}
\item For every $\alpha$ and $i\in [d]$, we add a \emph{directed} edge from $\alpha$ to $C_i^{0}$ if $\alpha [i]=0$, and a directed edge from $\alpha$ to $C_i^{1}$ if $\alpha [i]=1$.
\item For every $\beta$, we add an (undirected) edge from $\beta_i$ to $C_i$ if $\beta [i]=1$.
\item  For every $\gamma$ and $i\in [d]$, we add an (undirected) edge from $C_i$ to $\gamma$ if $\gamma [i]=1$.
\end{itemize}
Moreover, there will be some (undirected) edges that are independent of the vectors.
For every $\beta$, we have an edge of capacity $1$ from $C_i^{0}$ to ${\beta}'$, and an edge of capacity $1$ from $C_i^{1}$ to $\beta_i$.
Also, for every $\beta$, we have an edge from $\beta_i$ to $\beta'$, and an edge from ${\beta}'$ to $v_B$.
Finally, for every $\gamma$, we have an edge from $v_B$ to $\gamma\in V_3$. (Unless specified otherwise, these edges have no capacity constraints.)

The graph built has $N=n+2d+n\cdot d+n+1+d+n=\Theta(nd)$ nodes, at most $O(nd)$ edges, all of its capacities are in $[N]$, and its construction time is $O(nd)$.

\medskip
The following two claims
prove the correctness of this intermediate reduction.

\begin{claim}\label{claim:simple}
If every triple of vectors in $(U_1, U_2, U_3)$ has inner product at least $1$, then for all pairs $\alpha \in V_1,\gamma \in V_3$ the maximum-flow in $G'$ is at least $n\cdot d$.
\end{claim}

\begin{proof}
Assume that every triple of vectors in $(U_1, U_2, U_3)$ has inner product at least $1$, and fix some $\alpha$ and $\gamma$.
We will explain how to send $n\cdot d$ units of flow from $\alpha$ to $\gamma$ in $G'$.
By the assumption, for every $\beta$ there exist an $i\in [d]$ such that $\alpha[i]=\beta[i]=\gamma[i]=1$, and denote this index by $i_{\beta}$.
Each $i_{\beta}$ induces a path $(\alpha\rightarrow C_{i_{\beta}}^1\rightarrow\beta_{i_{\beta}}\rightarrow C_{i_{\beta}}\rightarrow \gamma)$ from $\alpha$ to $\gamma$, 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 $\beta'$.

We claim that for every $\beta$, an additional amount of $(d-1)$ units can pass through $\beta'$, which would add up to a total flow of $n(d-1)+n=nd$, concluding the proof. Indeed, for every $\beta$, we send flow in the following way. For every $i\in [d]\setminus i_{\beta}$, if $\alpha[i]=1$ then we send a single unit through $(\alpha\rightarrow C_i^1\rightarrow \beta_i\rightarrow \beta' \rightarrow  v_B\rightarrow \gamma)$, and otherwise we send a unit of flow through $(\alpha\rightarrow C_i^0\rightarrow \beta'\rightarrow v_B\rightarrow \gamma)$.

Since we defined the flow in paths, we only need to show that the capacity constraints are satisfied. Nodes of the form $C_i$ 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 $v_B$ is only used in the second phase and has $n(d-1)$ units of flow passing through it, just as its capacity.
For every $\beta$ and $i=i_{\beta}$, we pass in the first phase a single unit of flow through $\beta_i$. For every $\beta$ and $i\neq i_{\beta}$, we transfer in the second phase a unit of flow through $\beta_i$ if and only if $\alpha[i]=1$, thus it is bounded. For every $\beta'$, we pass in the second phase exactly $(d-1)$ units of flow through $\beta'$, preserving its capacity. For every $C_i^j\in N(\alpha)$,
where for a node $x$ we denote by $N(x)$ the set of nodes adjacent to $x$,
with $i\in [d]$ and $j\in \{0,1\}$, we pass a total of $n$ units of flow to nodes in $V_2$, one unit on each edge, thus the capacities are preserved, concluding the proof.
\end{proof}

\begin{claim}
If there is a triple of vectors $(\alpha_{\Phi}, \beta_{\Phi}, \gamma_{\Phi})\in (U_1, U_2, U_3)$ whose inner product is $0$, then the maximum-flow in $G'$ from $\alpha_{\Phi} \in V_1$ to $\gamma_{\Phi} \in V_3$ is at most $nd-1$.
\end{claim}

\begin{proof}
Assume for contradiction that there exists such a flow of value at least $nd$, and denote it by $f$.
Let $f=\{p_1,...,p_{\card{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(\alpha_{\Phi})$ sums up to $nd$ exactly.
Therefore, $f$ must have all of the nodes in $N(\alpha_{\Phi})$ saturated.

Consider a node $C_i^j\in N(\alpha_{\Phi})$ for some $i\in [d]$ and $j\in \{0,1\}$.
Note that $C_i^j$ is saturated in $f$ while its capacity is $n$ and it has exactly $n$ edges adjacent to it (excluding the edges incoming from $V_1$) of capacity $1$ each.
Therefore, we get that every node in $N(C_i^j)\setminus V_1$ must receive a single unit of flow from $C_i^j$ in $f$.
Hence, every $\beta$-cloud, which we define as all the nodes that are associated with a $\beta$, must have exactly $d$ flow paths in $f$ for which it is the first $\beta$-cloud that they pass through. We call this a \textit{first passing} of a path through a $\beta$-cloud.
In particular, for every $\beta$ and for every $i\in [d]$ such that $\alpha_{\Phi}[i]=1$ there must be a path $p_{\beta,i}$ in $f$ whose prefix is $(\alpha_{\Phi}, C_i^1, \beta_i,...)$.

Our main claim is that the $\beta_{\Phi}$-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 ${\beta_{\Phi}}'$ (whose capacity is only $d-1$), so name this path $p'$.
We will argue that this path must be in conflict with one of the $p_{\beta,i}$ paths described above.

For some $i\in [d]$ the prefix of $p'$ must be $(\alpha_{\Phi}, C_i^1, \beta_{\Phi_i}, C_i,...)$, since this is the only way it can avoid the node ${\beta_{\Phi}}'$.
This can only happen for an $i \in [d]$ for which $\alpha[i]=\beta[i]=1$, or else those edges will not exist in $G$.
But since $(\alpha_{\Phi}, \beta_{\Phi}, \gamma_{\Phi})$ is a triple whose inner product is $0$, it must be that $\gamma_{\Phi} [i]=0$ and so the edge $\{C_i,\gamma\}$ is not in the graph.
%
Hence, after $C_i$ this path can only go to a node $\widetilde{\beta}_i$ for some $\widetilde{\beta}$, and the (longer) prefix of $p'$ must be $(\alpha_{\Phi}, C_i^1, \beta_i, C_i, {\widetilde{\beta}}_i ,...)$.
Note that this is the same index $i$, and we know that $\alpha_{\Phi} [i] =1$.
Therefore, by the above, we know that there is another path $p_{\widetilde{\beta},i}$ in $f$ that has ${\widetilde{\beta}}_i$ as the third node on the path.
(That is, there is already a path that is first-passing through ${\widetilde{\beta}}_i$.)
This is a contradiction to the fact that the capacity of ${\widetilde{\beta}}_i$ is $1$.
\end{proof}


\paragraph{The final construction.}

The main issue with avoiding the directions on the edges between nodes in $V_1$ and $A$, is that additional $\alpha$'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 $V_1\cup V_3$ by $2n$. This is how we get our final graph $G$ from $G'$.
In the following we show how this modification concludes the proof of \expref{Lemma}{ProofsCapLemma}.


\begin{claim}\label{claim:first}
If every triple of vectors in $(U_1, U_2, U_3)$ has inner product at least $1$, then for all pairs $\alpha \in V_1,\gamma \in V_3$ the maximum-flow in $G$ is at least $2n^2d$.
\end{claim}
\begin{proof}
Since the flow that was defined in~\expref{Claim}{claim:simple} does not touch nodes in $V_1\cup V_3$, considering the same flow in $G$ but multiplied by $2n$, we get a new flow that is of size $nd\cdot(2n)$, concluding the proof.
\end{proof}

\begin{claim}\label{claim:second}
If there is a triple of vectors $(\alpha_{\Phi}, \beta_{\Phi}, \gamma_{\Phi})\in (U_1, U_2, U_3)$ whose inner product is $0$, then the maximum-flow in $G$ from $\alpha_{\Phi} \in V_1$ to $\gamma_{\Phi} \in V_3$ is at most $2n^2d -1$.
\end{claim}
\begin{proof}
Let $f$ be the maximum flow from $\alpha_{\Phi}$ to $\gamma_{\Phi}$ in $G$.
The paths in $f$ can be divided into two kinds: paths that pass through nodes in $(V_1\cup V_3)\setminus \{\alpha_{\Phi},\gamma_{\Phi}\}$, and paths that do not.
The total contribution of paths of the first kind can be upper bounded by the size of $(V_1\cup V_3)\setminus \{\alpha_{\Phi},\gamma_{\Phi}\}$, 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 $G'$ and can therefore be used in $G'$, 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 $G'$, which is $(nd-1)(2n)$.
Thus, the overall flow is at most $(nd-1)(2n)+2n-2=2n^2d-2$, which proves~\expref{Claim}{claim:second}.
\end{proof}
Since we showed a gap of at least one unit of flow between the yes and the no instances, the proof of \expref{Lemma}{ProofsCapLemma} is concluded.
\end{proof}



\section{Open problems}\label{Section:Conclusion}

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.

\begin{itemize}
\item Can we break the $O(mn)$ barrier also when the graphs have arbitrary (polynomial) capacities? Our result gives hope that this may be possible.

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

\smallskip
\textbf{Note added in proof.}
Ongoing work by the current authors indeed provides such a reduction but only for the sparse case.
%

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

\item Can we prove any conditional lower bound for \APMF 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.
\end{itemize}

%
\section{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 \MF.


\bibliographystyle{tocplain}

%
%
%
%
\bibliography{bibstrings,v017a005,bibtail}

%
%
%
%
%
\begin{tocauthors}
\begin{tocinfo}[abboud]
 Amir Abboud\\
  Department of Computer Science and Applied Mathematics\\
%
  Senior Scientist\\  %
  The Weizmann Institute of Science\\
  Rehovot, Israel\\  %
  amir.abboud\tocat{}weizmann\tocdot{}ac\tocdot{}il \\
 \url{http://weizmann.ac.il/math/AmirAbboud/home}      %
\end{tocinfo}
\begin{tocinfo}[krauthgamer]
  Robert Krauthgamer\\
  Professor\\        %
  Department of Computer Science and Applied Mathematics\\
  The Weizmann Institute of Science\\
  Rehovot, Israel\\ %
  robert.krauthgamer\tocat{}weizmann\tocdot{}ac\tocdot{}il \\
  \url{http://www.wisdom.weizmann.ac.il/~robi/}
\end{tocinfo}
\begin{tocinfo}[trabelsi]
  Ohad Trabelsi\\
  Postdoc\\            %
  Department of Electrical Engineering and Computer Science\\
  University of Michigan\\
  Ann Arbor, USA\\
  %
  ohadt\tocat{}umich\tocdot{}edu \\
  \url{http://sites.google.com/view/ohadtrabelsi/}
\end{tocinfo}
\end{tocauthors}

%
%
%
%
%
%
%
%
%
%
%
%
%
%
\begin{tocaboutauthors}
\begin{tocabout}[abboud]  %
\textsc{Amir Abboud} received his \phd\ at
\href{https://www.stanford.edu/}{Stanford University} in 2017 under
\href{https://people.csail.mit.edu/virgi/}{Virginia Vassilevska
Williams}.
He was subsequently a Research Staff Member at the
\href{http://www.almaden.ibm.com/software/disciplines/pm/}{theory
group} in the \href{http://www.almaden.ibm.com/}{IBM Almaden Research
  Center}. Since 2021, he
%
has been  %
a faculty member at the
\href{http://www.weizmann.ac.il/}{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
\href{https://en.wikipedia.org/wiki/FC_Barcelona_2%
%
14, 2020}  %
his favorite team was FC Barcelona.
%

\end{tocabout}
\begin{tocabout}[krauthgamer]
  \textsc{Robert Krauthgamer}
(called ``Robi'' by his friends and colleagues) %
received his \phd\ at the \href{http://www.weizmann.ac.il/}{Weizmann Institute of Science} in 2001 under \href{http://www.wisdom.weizmann.ac.il/~feige/}{Uriel Feige}. He was
%
%
subsequently a postdoc in \href{http://www.eecs.berkeley.edu/Research/Areas/THY/}{Berkeley's theory group}, and then a Research Staff Member at the \href{https://researcher.watson.ibm.com/researcher/view_group.php?id=4207}{theory group} in the \href{http://www.almaden.ibm.com/}{IBM Almaden Research Center}. %
Since 2007, he
%
has been   %
a faculty member
at the \href{http://www.weizmann.ac.il/}{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 \href{http://en.wikipedia.org/wiki/Sea_of_Galilee}{Sea of Galilee} in a 10\,km competitive race, and was the last one to arrive at the finish line.
\end{tocabout}
\begin{tocabout}[trabelsi]
  \textsc{Ohad Trabelsi} received his \phd\ at the \href{http://www.weizmann.ac.il/}{Weizmann Institute of Science} under \href{http://www.wisdom.weizmann.ac.il/~robi/}{Robert Krauthgamer}. He was subsequently a postdoc in the same group. Since then, he has been a postdoc at the \href{http://eecs.engin.umich.edu/}{Department of Electrical Engineering and Computer Science} %
at %
the \href{http://umich.edu/}{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.
\end{tocabout}

\end{tocaboutauthors}

\end{document}
