1.
Introduction:
2.
Approach:
3.
FAQs:
4.
Key Takeaways:
Last Updated: Mar 27, 2024

# Minimum Cut on a Graph Using a Maximum Flow Algorithm

Nishant Rana
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## 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:-

1. 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.
2. 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.

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.

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## FAQs:

1. 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.
2. 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:

1. We first discussed the approach to finding the Minimum Cut on a Graph Using a Maximum Flow Algorithm.
2. 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.

Live masterclass