# Max-flow min-cut theorem

 related topics {math, number, function} {line, north, south} {math, energy, light} {system, computer, user} {ship, engine, design}

In optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the minimum capacity which when removed in a specific way from the network causes the situation that no flow can pass from the source to the sink.

The max-flow min-cut theorem is a special case of the duality theorem and can be used to derive Menger's theorem and the König-Egerváry Theorem.

## Contents

### Definition

Let N = (V,E) be a network (directed graph) with s and t being the source and the sink of N respectively.

The maximum flow problem is to maximize | f |, that is, to route as much flow as possible from s to the t.

The minimum cut problem is to minimize c(S,T), that is, to determine S and T such that the capacity of the S-T cut is minimal.

### Statement

The max-flow min-cut theorem states

### Linear program formulation

The max-flow problem and min-cut problem can be formulated as two primal-dual linear programs.

Max-flow (Primal)

Min-cut (Dual)

maximize $|f| = \sum_{j: (s, j) \in E} f_{sj}$

minimize $\sum_{(i, j) \in E} c_{ij} d_{ij}$

subject to

$\begin{array}{rclr} f_{ij} & \leq & c_{ij} & (i, j) \in E \\ \sum_{j: (i, j) \in E} f_{ij} - \sum_{j: (j, i) \in E} f_{ji} & \geq & 0 & i \in V, i \neq t \\ f_{ij} & \geq & 0 & (i, j) \in E\\ \end{array}$

subject to

$\begin{array}{rclr} d_{ij} - p_i + p_j & \geq & 0 & (i, j) \in E \\ p_s & = & 1 & \\ p_t & = & 0 & \\ p_i & \geq & 0 & i \in V \\ d_{ij} & \geq & 0 & (i, j) \in E \end{array}$

The equality in the max-flow min-cut theorem follows from the strong duality theorem, which states that if the primal program has an optimal solution, x*, then the dual program also has an optimal solution, y*, such that the optimal values formed by the two solutions are equal.