Fast Maximum Matching Algorithm for Bipartite Graphs

Question

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.

Answer 1

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.