  Recently, many studies have been devoted to finding \textit{diverse}
solutions in classical combinatorial problems, such as \textsc{Vertex Cover}
(Baste et al., IJCAI'20), \textsc{Matching} (Fomin et al., ISAAC'20) and
\textsc{Spanning Tree} (Hanaka et al., AAAI'21). We initiate the algorithmic
study of $k$-\textsc{Diverse Minimum s-t Cuts} which, given a directed graph $G
= (V, E)$, two specified vertices $s,t \in V$, and an integer $k > 0$, asks for
a collection of $k$ minimum $s$-$t$ cuts in $G$ that has maximum diversity. We
investigate the complexity of the problem for maximizing three diversity
measures that can be applied to a collection of cuts: (i) the sum of all
pairwise Hamming distances, (ii) the cardinality of the union of cuts in the
collection, and (iii) the minimum pairwise Hamming distance. We prove that
$k$-\textsc{Diverse Minimum s-t Cuts} can be solved in strongly polynomial time
for diversity measures (i) and (ii) via \textit{submodular function
minimization}. We obtain this result by establishing a connection between
ordered collections of minimum $s$-$t$ cuts and the theory of distributive
lattices. When restricted to finding only collections of mutually disjoint
solutions, we provide a more practical algorithm that finds a maximum set of
pairwise disjoint minimum $s$-$t$ cuts. For graphs with small minimum $s$-$t$
cut, it runs in the time of a single \textit{max-flow} computation. Our results
stand in contrast to the problem of finding $k$ diverse \textit{global} minimum
cuts -- which is known to be NP-hard even for the disjoint case (Hanaka et al.,
AAAI'23) -- and partially answer a long-standing open question of Wagner
(Networks, 1990) about improving the complexity of finding disjoint collections
of minimum $s$-$t$ cuts. Lastly, we show that $k$-\textsc{Diverse Minimum s-t
Cuts} subject to diversity measure (iii) is NP-hard already for $k=3$.
