Run-time of Hungarian algorithm - matrix formulation

There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a spreadsheet.

The problem is, I could not understand the argument of why this algorithm, in its matrix formalism, is polynomial in $$n$$. In particular, in the above presentation, I got stuck trying to prove that Step 5 (page 13) is executed $$O(n)$$ times, or more generally, $$O(poly(n))$$ times.

In step 5, we subtract a number $$x$$ from each uncovered row, and then add the same $$x$$ to each covered column. Since in this step, the size of the covering is less than $$n$$, there are more uncovered rows than covered columns, so we subtract $$x$$ more times than we add $$x$$. Hence, the sum of all elements in the matrix strictly decreases each time. Since the sum always remains positive, the algorithm must eventually end.

However, I could not understand why it must end after $$O(poly(n))$$ iterations.

What am I missing in the above argument?

• Did you actually see the conclusion of "$O(n)$ iterations" anywhere? – John L. Jan 31 '19 at 22:10
• @Apass.Jack no, I just remembered that the total runtime complexity should be $O(n^3)$ and each iteration might take time $O(n^2)$, so I concluded that there must be $O(n)$ iterations. In any case, I do not even understand why there must be $O(poly(n))$ iterations? – Erel Segal-Halevi Feb 1 '19 at 6:08

However, I could not understand why it must end after $$𝑂(n)$$ iterations.

Because it is not true.

Check the following matrices, which are the initial matrix, the matrix at the end of step 2, and the matrices at the end of step 5. Here the steps are explained as in the notes mentioned in the question.

[[1, 1, 1, 1, 1]
[1, 2, 11, 11, 11]
[1, 3, 4, 11, 11]
[1, 4, 6, 7, 11]
[1, 5, 8, 10, 11]]

[[0, 0, 0, 0, 0]
[0, 1, 10, 10, 10]
[0, 2, 3, 10, 10]
[0, 3, 5, 6, 10]
[0, 4, 7, 9, 10]]

[[0, 0, 0, 0, 0]
[0, 0, 9, 9, 9]
[0, 1, 2, 9, 9]
[0, 2, 4, 5, 9]
[0, 3, 6, 8, 9]]

[[0, 0, 0, 0, 0]
[0, 0, 9, 9, 9]
[0, 0, 1, 8, 8]
[0, 1, 3, 4, 8]
[0, 2, 5, 7, 8]]

[[0, 0, 0, 0, 0]
[0, 0, 8, 8, 8]
[0, 0, 0, 7, 7]
[0, 1, 2, 3, 7]
[0, 2, 4, 6, 7]]

[[0, 0, 0, 0, 0]
[0, 0, 8, 8, 8]
[0, 0, 0, 7, 7]
[0, 0, 1, 2, 6]
[0, 1, 3, 5, 6]]

[[0, 0, 0, 0, 0]
[0, 0, 7, 7, 7]
[0, 0, 0, 7, 7]
[0, 0, 0, 1, 5]
[0, 1, 2, 4, 5]]

[[0, 0, 0, 0, 0]
[0, 0, 7, 6, 6]
[0, 0, 0, 6, 6]
[0, 0, 0, 0, 4]
[0, 1, 2, 3, 4]]


So, the number of times step 5 can be executed can be as big as $$\frac12(n-2)(n-1)$$.

• Step 2: "Subtract the smallest entry in each column from all the entries of its column." I fail to see in which part of your trace you applied this step to column 5. After Step 2, each column (as well as each row) should contain a zero. – Vincenzo Jan 31 '19 at 22:25
• Wait, not correct yet. – John L. Jan 31 '19 at 23:00
• Interesting example, thanks! Are $O(n^2)$ iterations always sufficient? – Erel Segal-Halevi Feb 1 '19 at 6:09

It is at least easy to see that it must end after $$O(n^2)$$ iterations.

Let $$r$$ be the row containing the smallest uncovered element. Each time you execute step 5, at least one positive element of $$r$$ becomes zero, while covered zero elements of $$r$$ remain zero (since you add back what you subtracted). Also, by construction there cannot be uncovered zero elements in $$r$$. Hence the number of zero elements in $$r$$ increases by one. This can happen $$n$$ times for each row.

For the $$O(n)$$ bound, I think one should be able to prove that the number of minimal lines required to cover the zeros increases by at least one at each step. However the proofs I know are typically based on a different presentation of the algorithm, see for example: Golin, M. Bipartite Matching & the Hungarian Method.

• $O(n^2)$ is also fine. But I do not understand the argument: step 5 adds a zero to row $r$, but, it may also make a covered zero in another row positive. How do we know that the total number of zeros in the matrix always increases? – Erel Segal-Halevi Jan 31 '19 at 20:10