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?