Min Cut Calculator

Pseudocode

The minimum cut is not computed directly. You compute a maximum flow, then read the cut off the residual graph in a single traversal.

MinCut(graph, s, t):
    run any max-flow algorithm to saturation

    // S = everything still reachable from s
    // in the RESIDUAL graph
    S = BFS/DFS from s using only edges with
        residual capacity > 0
    T = all remaining vertices

    cut = { (u,v) in original edges :
            u in S and v in T }
    return cut, sum of original capacities in cut

Two facts make this work. Every edge crossing from S to T must be saturated, otherwise its residual capacity would be positive and its endpoint would have been reachable, putting it in S. And every edge from T back to S must carry zero flow. So the flow across the cut equals the cut capacity exactly, and since no flow can exceed any cut, both must be optimal.

Worked example, step by step

Find the minimum cut on the same network used for maximum flow, by reading the residual graph once the flow is saturated.

Example graph: Directed capacities S to A (10), S to B (10), A to B (2), A to T (4), B to T (9).

1. Compute the max flow. Augmenting along S to A to T pushes 4, and along S to B to T pushes 9. Total flow is 13 and no augmenting path remains.
2. Look at the residual graph. S-A has 10 - 4 = 6 spare. S-B has 10 - 9 = 1 spare. A-B is untouched, so all 2 remain. A-T and B-T are both fully saturated with 0 spare.
3. Find S by traversal. Start at S. The S-A edge has spare capacity, so A joins S. From A, the A-B edge has spare capacity, so B joins S. From B, the only outgoing edge B-T is saturated. Nothing else is reachable, so S is the set {S, A, B}.
4. Read off the cut. T is the remaining vertex set, just {T}. The original edges running from S to T are A-T with capacity 4 and B-T with capacity 9.
5. Verify. The cut capacity is 4 + 9 = 13, exactly equal to the maximum flow. Removing those two edges leaves T unreachable from S, confirming it is a genuine cut.

The minimum cut is the edge pair A-T and B-T with total capacity 13, matching the maximum flow of 13. Note that S-A and S-B have a combined capacity of 20 and also form a cut, but a more expensive one. The bottleneck is at the sink side, and the residual traversal finds it without any searching over candidate cuts.

Complexity, and where it comes from

Time: same as the max-flow algorithm used · Space: O(V + E)

The cut extraction itself is a single graph traversal at O(V + E), which is negligible. All the cost sits in the maximum-flow computation that precedes it: O(V times E squared) with Edmonds-Karp, or O(V squared times E) with Dinic. This is worth stating plainly because it explains why minimum cut is not treated as a separate problem. There is no known way to find the minimum s-t cut that is asymptotically faster than computing the maximum flow, since by the max-flow min-cut theorem the two are the same computation viewed from opposite sides.

When to use Minimum Cut, and when not to

The word "cut" covers several genuinely different problems. Choosing the wrong one is the most common mistake here.

Common pitfalls

• Traversing the original graph instead of the residual graph. The cut is defined by what is reachable using leftover capacity, not by the original edges. Running the traversal on the original graph typically reaches the sink and yields no cut at all. This is the most common implementation error.
• Confusing the minimum s-t cut with the global minimum cut. The s-t cut separates two chosen vertices. The global minimum cut separates the graph into any two nonempty parts and needs Stoer-Wagner or Karger. Solving the wrong one gives a valid answer to a question nobody asked.
• Assuming the minimum cut is unique. Its capacity is unique; the edge set often is not. Several distinct cuts can share the minimum capacity, and which one you get depends on the flow found. Tests should assert the capacity, not a specific edge list.
• Counting edges from T back to S. Only edges going from the S side to the T side count toward the cut capacity. Reverse edges carry zero flow across the cut and contribute nothing. Including them inflates the answer above the max flow and breaks the theorem.
• Forgetting that capacities must be nonnegative. The max-flow min-cut correspondence assumes nonnegative capacities. Negative capacity is not a meaningful notion of throughput, and the residual reasoning collapses without it.

Frequently asked questions

What is a minimum cut in a graph?

A cut is a partition of the vertices into two sets, one containing the source and one containing the sink, and its capacity is the total capacity of the edges crossing from the source side to the sink side. The minimum cut is the cheapest such partition, which identifies the bottleneck: the least expensive set of edges to remove in order to disconnect source from sink.

How do you find the minimum cut?

Compute the maximum flow, then run a BFS or DFS from the source in the residual graph, following only edges that still have spare capacity. The vertices you reach form one side of the cut, everything else forms the other, and the original edges crossing between them are the minimum cut.

What is the max-flow min-cut theorem?

It states that the maximum flow from source to sink always equals the capacity of the minimum cut separating them. No flow can exceed any cut, since all flow must cross it, and when no augmenting path remains the residual-reachable set defines a cut whose capacity the flow exactly meets, so the two values coincide.

What is the difference between minimum cut and global minimum cut?

A minimum s-t cut separates two specified vertices and is found via maximum flow. A global minimum cut separates the graph into any two nonempty parts with no vertices designated in advance, and is found with Stoer-Wagner or Karger. A global cut can be much cheaper than any particular s-t cut.

What is minimum cut used for?

Identifying network vulnerabilities and single points of failure, image segmentation where pixels are vertices and the cut separates foreground from background, clustering and community detection, project selection problems, and reliability analysis of communication or transport infrastructure.