Fast Maximum Matching Algorithm for Bipartite Graphs

4
votes

I am trying to solve the following problem but my algorithm is too slow. That's because I am using Edmonds - Karp algorithm to find maximum flow which when applied to bipartite graphs gives maximum matching as well. It's running time is n^5. I would like to know any faster algorithms to solve this problem (for bipartite graphs specifically). One algorithm that I am currently studying is Relabel to Front which is n^3.

3
algorithmgraphmatchingbipartitenetwork-flow
This algorithm, which is an efficient Ford-Fulkerson implementation, has an O(n^3) runtime - Niklas B.
I get AC in 0.018 seconds with that. - Niklas B.
Oh thanks Niklas ! As usual you solved it again lol ! Alright, I will debug your code to understand it but I thought we should not be using Ford Fulkerson because it uses DFS. Instead we should use BFS for finding augmenting paths. On the other hand, looks like your approach is doing lot more than just finding augmenting paths as I see "greedy matching in comment". - Varun Sharma
No I didn't use a greedy matching. And DFS is in fact better for bipartite matching for some reason - Niklas B.
you mean your algorithm is just plain ford-fulkerson? just keep on finding augmenting paths till you can't find anymore? - Varun Sharma

3 Answers

7
votes

I write bipartite matching using dinitz's algorithm. Also there is a theorem that for the graphs of the type of the maximum bipartite matching problems it has the same complexity as relabel to front(and it is way easier to implement).

In networks arising during the solution of bipartite matching problem, the number of phases is bounded by O(\sqrt{V}), therefore leading to the O(\sqrt{V} E) time bound. The resulting algorithm is also known as Hopcroft–Karp algorithm. More generally, this bound holds for any unit network — a network in which each vertex, except for source and sink, either has a single entering edge of capacity one, or a single outgoing edge of capacity one, and all other capacities are arbitrary integers.

Unfortunately the wikipedia article on the algorithm is way not enough to implement it and I could not find any better resource online. I have my own implementation, but I have created it using guidance from others in my university a long time ago.

2
votes

The so-called Hungarian algorithm for bipartite matching can be implemented with a lower runtime complexity.

1
votes

Hopcroft–Karp algorithm provides the lowest time complexity for finding maximum matching (or minimum vertex cover) for Bipartite graph.

According to wikipidea, It runs in O(E * (V^0.5)), E is the total edges and V is the total vertices. At worst case (dense graph) this will be O(V^2.5).