最小カット問題(minimum cut, min cut)とは、非負の重みのついた有向グラフ$G = (V, E)$と2つの頂点$s, t$が与えられた時、 辺の部分集合$S \subseteq E$であって、$G' = (V, E \setminus S)$上で$s$から$t$へのパスが存在しないようなもの(これを"s-t-カット"という)のうち、 重み$w(S) = \sum_{v \in S} w(v)$を最小化する最適化問題である。

最大流問題のLP双対が最小カット問題の自然なLP緩和となる。このLPは整数性を持つ。 よって、最大流の容量と最小カットの重みは等しい(Max-flow min-cut theorem)。 よって、最大流問題を解くアルゴリズムによって最小カット問題は効率的に解ける。

最大流の解からは、残余グラフ上で$s$から到達できる頂点集合を$S$とすれば最小カットの解を復元できる。 最大流問題を解くアルゴリズムによっては(Push-relabel法など)、最大流の解を求めきる前に最小カットの解が求まることがある。この場合、途中で終了するようにすれば高速化になる。