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