Minimum Cut on a Graph Using a Maximum Flow Algorithm

Introduction:

We are given a graph with N nodes. We need to find the minimum cut on the graph using the maximum flow algorithm.

Let us first discuss what is Minimum Cut in a graph:

The cut is a set of edges of a graph. If we remove these sets of edges from the graph, then that graph gets divided into two disjoint subsets.

An s-t cut is a cut that divides the source ‘s’ and the sink ‘t’ into different subsets. It will contain the edges going from the source’s side to the sink’s side. The capacity of the s-t cut is equal to the sum of the weight of each edge in the cut set.

In the above graph C1, C2, and C3 are the three different minimum cuts we can make. The weight of each of them is 14. Hence, we need to find the edges of one of the minimum cuts.

Approach:

The max-flow min-cut theorem states that in a flow network, the amount of maximum flow is equal to the capacity of the minimum cut. See here for proof of this theorem.

Let us first see a few concepts which we will use:-

Residual Graph: Residual graph is a graph of a network flow that indicates if the additional flow is possible or not. If there is a path between the source node and the sink node in the residual graph, then that means the additional flow is possible. The weight of the edges of the residual graph indicates the residual capacity of that edge. The residual capacity of an edge is the original capacity minus the current flow.
Ford Fulkerson algorithm: Ford-Fulkerson is a greedy algorithm that is useful to find the maximum flow of a network flow. It finds all the valid flow paths from the source node to the sink node until none is left and then adds them up. You can refer to this blog for more.

We will use the concept of the residual graph to print all the edges of the minimum cut set.

We follow these steps:-

1) We will run the Ford-Fulkerson algorithm and find the final residual graph.

2) We will then find those vertices that can be reached from the source in the residual graph.

3) The edges that point from a reachable vertex to a non-reachable vertex are part of minimum cut edges. In the end, we will print all such edges.

Refer to the below implementation of the above approach.

import java.util.*;

public class Graph {

  /*
This function will return true if
it find a path from source 's' to
sink 't'. It will also fill the
parent[] to store the path.
*/
  private static boolean bfs(int[][] residualGraph, int s, int t, int[] parent) {

  /*
Creating a visited array
to check if the current node
is visited or not.
*/
  boolean[] visited = new boolean[residualGraph.length];

  /*
Initializing a queue and adding
source vertex to the queue and
marking it visited.
*/
Queue<Integer> q = new LinkedList<Integer>();
q.add(s);
visited[s] = true;
parent[s] = -1;

  // Standard BFS Loop
  while (!q.isEmpty()) {
  int v = q.poll();
  for (int i = 0; i < residualGraph.length; i++) {
  if (residualGraph[v][i] > 0 && !visited[i]) {
q.offer(i);
visited[i] = true;
parent[i] = v;
}
}
}

  /*
Return true if we reach the
sink node starting from the
source node.
*/
  return (visited[t] == true);
}

  /*
This function will help us
to find all the reachable
vertices from source. It will
mark those nodes visited is we
can reach that node from source.
*/
  private static void dfs(int[][] residualGraph, int s, boolean[] visited) {
visited[s] = true;
  for (int i = 0; i < residualGraph.length; i++) {
  if (residualGraph[s][i] > 0 && !visited[i]) {
dfs(residualGraph, i, visited);
}
}
}

  // This function will print the minimum s-t cut
  private static void minCut(int[][] graph, int s, int t) {
  int u,v;

  int[][] residualGraph = new int[graph.length][graph.length];
  for (int i = 0; i < graph.length; i++) {
  for (int j = 0; j < graph.length; j++) {
residualGraph[i][j] = graph[i][j];
}
}

  // This array is filled by BFS and to store path
  int[] parent = new int[graph.length];

  // Augment the flow until there is path from source to sink
  while (bfs(residualGraph, s, t, parent)) {

  /*
Find minimum residual capacity of the edges
along the path filled by BFS. Or we can say
find the maximum flow through the path found.
*/
  int pathFlow = Integer.MAX_VALUE;
  for (v = t; v != s; v = parent[v]) {
u = parent[v];
pathFlow = Math.min(pathFlow, residualGraph[u][v]);
}

  for (v = t; v != s; v = parent[v]) {
u = parent[v];
residualGraph[u][v] = residualGraph[u][v] - pathFlow;
residualGraph[v][u] = residualGraph[v][u] + pathFlow;
}
}

  // Flow is maximum now, find vertices reachable from s
  boolean[] isVisited = new boolean[graph.length];
dfs(residualGraph, s, isVisited);

  /*
Printing the edges that point
from a reachable vertex to a
non-reachable vertex in orginal graph.
*/
  for (int i = 0; i < graph.length; i++) {
  for (int j = 0; j < graph.length; j++) {
  if (graph[i][j] > 0 && isVisited[i] && !isVisited[j]) {
System.out.println(i + " - " + j);
}
}
}
}
}

Time Complexity: We are running a BFS on the Graph which takes O(E) time where E is the number of edges in the Residual Graph. For each edge, the flow in the worst case will reach its maximum value(let us say F). Hence, we will iterate the BFS algorithm F times. Hence, the overall time complexity is O(F * E).

Space Complexity: We are creating a Residual Graph, visited array, and maintaining a queue. All of them will contribute O(N) space complexity.

FAQs:

What is the Cut Set?
- The cut is a set of edges of a graph. If we remove these sets of edges from the graph, then that graph gets divided into two disjoint subsets.
What is the Ford-Fulkerson algorithm?
- The Ford-Fulkerson algorithm helps to find the maximum flow in the graph. The algorithm will begin with the empty flow, and at every step, it will find a path going from the source vertex to the sink vertex that generates more flow.

Key Takeaways:

In this blog, we have covered the following things:

We first discussed the approach to finding the Minimum Cut on a Graph Using a Maximum Flow Algorithm.
Then we saw how to implement the approach discussed.

If you want to learn more about Graphs and want to practice some questions which require you to take your basic knowledge on Graphs a notch higher, then you can visit our Guided Path for Graphs.

Until then, All the best for your future endeavors, and Keep Coding.