# Max flow problem

In a network, $LaTeX: [V, A],$ there are two special nodes in $LaTeX: V:$ a source $LaTeX: (s)$ and a sink $LaTeX: (t)$. The problem is to maximize the flow from $LaTeX: s$ to $LaTeX: t$ subject to conservation of flow constraints at each node and flow bounds on each arc. The max flow labeling algorithm provides a constructive proof of the Max flow - Min cut theorem.

This can also be obtained from the duality of the following linear program:

maximize $LaTeX: v:$

$LaTeX: 0 \le x_{ij} \le U_{ij}$ for $LaTeX: (i, j) \in A$;

$LaTeX: \sum_j x_{ij} - \sum_j x_{ji} = 0$ for $LaTeX: i \in V \backslash \{s,t\};$

$LaTeX: \sum_j x_{sj} - \sum_j x_{js} = v;$

$LaTeX: \sum_j x_{tj} - \sum_j x_{jt} = -v.$

$LaTeX: U$ are upper bounds (capacities) on arc flows, and each sum is for $LaTeX: j$ such that the indicated arc is in $LaTeX: A.$