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.