1
$\begingroup$

I am trying to understand the Hungarian algorithm for the assignment problem.

I found this presentation which gives an excellent explanation about the algorithm. However, there is one step I do not understand.

Step 3 (pages 13, 16) says "Cover all the zeros of the matrix with the minimum number of horizontal or vertical lines". How can this step be done in polynomial time?

I.e, given an $n\times n$ matrix with some zeros, what is an efficient algorithm for finding the smallest set of rows and/or columns that contain all the zeros?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

OK, after reading this much more complicated explanation of the same algorithm, using bipartite graphs instead of matrices, I realized how to find the smallest number of rows/cols.

Given the matrix, create the "graph of zeros" - a bipartite graph where the rows are on one side and the cols are on the other side, and there is an edge between row and column iff there is a zero in their intersection. Then, our problem becomes finding a smallest vertex covering of this graph.

Based on Koenig's theorem, a smallest vertex covering in a bipartite graph can be found using any algorithm for finding a largest matching in the graph, in polynomial time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hey Erel, do you perhaps have code or pseudo-code showing how that would work? $\endgroup$
    – CerebralFart
    Commented Feb 22, 2019 at 20:12
  • $\begingroup$ No, sorry... but in the Wikipedia pages there are many links to code, maybe some of them contains a similar idea $\endgroup$
    – Erel Segal-Halevi
    Commented Feb 24, 2019 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.