Does Hungarian algorithm have better time complexity than the Edmonds-Karp algorithm?

Question

Please note that I'm asking based on my current knowledge that I'm still not sure whether it's right or wrong, so please correct me if there's a mistake in my question 🙏

I'm currently working on a minimum-cost maximum-flow (MCMF) problem. What I know, Hungarian algorithm's time complexity is O(n^3) while the Edmonds-Karp algorithm's time complexity is O(VE^3). Now suppose I'm matching workers and jobs, where there are two workers and three jobs. Thus, the time complexity of Hungarian would be n^3 where n = number of workers and jobs so 5^3 = 125. Meanwhile, the Edmonds-Karp time complexity depends on the amount of vertices and edges, and what I know, to solve MCMF, a flow graph is required. If we create a flow graph from mentioned workers and jobs, we will have two additional vertices which are the source and sink vertices, so there are 7 vertices and 11 edges, right? So, the time complexity of Edmonds-Karp would be 7 * 11^2 = 847 which is way higher than Hungarian.

To be honest, I worry that there are still huge mistakes in my understanding above. Thank you for your concern.

Answer 1

A problem with two workers and three jobs can be represented as both a matrix:

	W1	W2
J1	C11	C21
J2	C12	C22
J3	C13	C23

and a graph:

*The Source and Sink nodes may or may not be represented in any graph you see for this problem, but they are included in Big O calculations.

The Hungarian Algorithm technically only works with an equal number of workers and jobs, but there are ways around that. For our purposes just know that the n in the Hungarian Algorithm's Big O time complexity is either the sum of the number of workers and jobs, or two times the maximum of the number of workers and the number of jobs (depending on how you modify the problem to fit). I will use the first option. In this example there are two workers and three jobs, so n is 5 and O(n³) is 5³ is 125.

The Big O time complexity of the Edmonds-Karp Algorithm is based on the graph representation of this problem. In graph notation the Vertices (V) are the nodes in the graph, and the Edges (E) are the lines connecting the vertices. In this example with two workers, three jobs, a source, and a sink, V is 7 and E is 11, so O(V​E²) is 7×11² is 847.

However, big O notation is about how the complexity changes as the input size increases, not just the complexity for a single problem. In order to compare the complexities of these algorithms we need to rewrite their notations using common values. For this we can use the number of workers (W) and the number of jobs (J). Doing this we get O((W+J)³) for the Hungarian Algorithm and O((W+J+2)(W+(W×J)+J)²) for the Edmonds-Karp Algorithm. I don't know a good way to show the graph comparison for two three dimensional graphs, so let's assume W equals J and compare O((2n)³) to O((2n+2)(2n+n²)²) instead:

So we can see that, yes, the Hungarian Algorithm has a better time complexity than the Edmonds-Karp Algorithm, for the Assignment Problem. This is because the Hungarian Algorithm was designed for the Assignment Problem (where every worker connects to every job), while the Edmonds-Karp Algorithm was designed for the Maximum Flow Problem. The Assignment Problem is a special case of the Transportation Problem, which is a special case of the Minimum Cost Flow Problem. The Maximum Flow Problem is also a special case of the Minimum Cost Flow Problem, but not as specialized as the Assignment Problem. It is possible to convert between them, but each algorithm is specialized for its own problem. If the number of edges is much smaller than the number of vertices (which can happen in the Maximum Flow Problem, but not the Assignment Problem), then the Edmonds-Karp Algorithm can be better than the Hungarian Algorithm.