# Min st-cut problem

Last edited: 2023-11-11

# 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