Finding min-cut in a flow network
Determining whether min-cut is unique
Finding maximum matching in bipartite graphs
This problem seems completely unrelated, but it is not! Let us see how one can solve it using max flow algorithms
Reduction from finding the maximum matching to finding the max flow
The following lemma then holds
And one more
In total, this gives us a way to compute maximum matching using max flow algorithms, namely Hopcroft-Karp that is specifically designed for flow networks with capacities of 1. The runtime is then