Min st-cut problem
programming
Statement
Min st-cut
Given a flow network $(G, c, s, t)$ what is the st-cut $(L, R)$ with minimum capacity.
Solutions
- Ford-Fulkerson Algorithm
- $O(C \vert E \vert)$ where $C$ is the min cut.
- This is only guaranteed to terminate for integer flows.
Theory
- Max-flow min-cut Theorem
- This says the solutions are the same as the max flow problems.