Minimum Cut

In graph theory, a Cut is a partition of the vertices of a graph into two disjoint subsets.

For a Flow Network with a specific Source ($S$) and Sink ($T$), an $S-T$ Cut splits the graph into two sets:

• Set $A$, which contains the Source $S$.
• Set $B$, which contains the Sink $T$.

The Capacity of the Cut is the sum of the capacities of all edges going from Set $A$ to Set $B$. (We ignore edges going backwards from B to A).

The Minimum Cut problem asks: What is the absolute minimum total capacity of edges we can remove from the graph to completely disconnect the Source from the Sink?

Real-Life Analogy

Think of Military Sabotage. An enemy wants to completely cut off the supply line between your Factory (Source) and the Frontlines (Sink) by blowing up bridges. However, they have limited explosives, and larger bridges require more explosives (Capacity/Weight). The enemy wants to find the specific set of bridges that perfectly severs the supply line using the absolute minimum amount of explosives. This is the Minimum Cut.

The Max-Flow Min-Cut Theorem

This is one of the most beautiful and profound theorems in computer science.

Theorem: The maximum amount of flow passing from the Source to the Sink is mathematically exactly equal to the capacity of the Minimum Cut.

Why? The bottleneck of the entire system (the maximum flow you can push through) is strictly dictated by the weakest link in the network (the minimum cut).

How to Find the Minimum Cut

Because of the theorem above, finding the Minimum Cut is incredibly easy if you already have the Ford-Fulkerson or Edmonds-Karp algorithm written!

Step 1: Run the Max Flow algorithm to generate the final Residual Graph. (Remember, the algorithm stops when there are no more paths from S to T with available capacity).

Step 2: Run a simple Breadth-First Search (BFS) starting from the Source $S$ on the final Residual Graph.

• You can only travel across edges that have a residual capacity $> 0$.
• Because Max Flow just finished, BFS will eventually hit a wall where capacity is 0. It will be impossible to reach the Sink $T$.
• Every node that BFS can reach belongs to Set A. Every node BFS cannot reach belongs to Set B.

Step 3: Look at the original graph. Any edge that originates in Set A and terminates in Set B is a Cut Edge! These are the specific bridges the enemy needs to blow up.

Finding Cut Edges (TypeScript Snippet)

Assuming rGraph is the final Residual Graph returned by Edmonds-Karp, and graph is the original capacity graph.

function findMinCut(graph: number[][], rGraph: number[][], source: number): void {
  const V = graph.length;
  const visited = new Array(V).fill(false);
  const queue: number[] = [source];
  
  // 1. Run BFS on the Residual Graph to find Set A
  visited[source] = true;
  while (queue.length > 0) {
    const u = queue.shift()!;
    for (let v = 0; v < V; v++) {
      // Only traverse edges with remaining capacity!
      if (!visited[v] && rGraph[u][v] > 0) {
        visited[v] = true;
        queue.push(v);
      }
    }
  }

  // 2. visited array now defines the subsets!
  // If visited[i] is true, node i is in Set A.
  // If visited[i] is false, node i is in Set B.

  console.log("Edges included in the Minimum Cut:");
  // 3. Find edges crossing from Set A to Set B in the ORIGINAL graph
  for (let i = 0; i < V; i++) {
    for (let j = 0; j < V; j++) {
      if (visited[i] && !visited[j] && graph[i][j] > 0) {
        console.log(`Edge ${i} -> ${j}`);
      }
    }
  }
}

Image Segmentation Application

Min-Cut is heavily used in Computer Vision for separating the "Foreground" (a person) from the "Background" in a photo. Pixels are modeled as nodes in a graph. Edges between pixels represent how similar they are in color. We connect all pixels to a "Source" (Foreground) and a "Sink" (Background). Running Min-Cut cleanly slices the graph, mathematically grouping similar pixels together and removing the background!