1
$\begingroup$

In Kuhn's algorithm for the maximum bipartite matching problem we iterate through the vertices of one partite set and try to build the increasing chain, starting with the current vertex. Once the traversal is completed, we claim that the maximal matching is found. But why don't we need to check again the vertices for which we weren't able to build the increasing chain? How can we prove that if for some vertex v it was not possible to build the increasing chain starting with v during the traversal, then we don't need to check v again? Why shouldn't we perform the second traversal?

$\endgroup$
  • $\begingroup$ Have you seen a proof of correctness for the algorithm? $\endgroup$ – Yuval Filmus May 11 '15 at 3:14
1
$\begingroup$

Kuhn's algorithm maintains the following invariant: after scanning through vertices $v_1,\ldots,v_k$ on the left, the current matching is a maximal matching of the graph consisting of $v_1,\ldots,v_k$ on the left, and the entire right-hand side. Hence at the end, we get a maximal matching of the entire graph.

How do we know that Kuhn's algorithm maintains the invariant? We prove it when we prove that Kuhn's algorithm is correct. I encourage you to find a correctness proof of the algorithm (such proofs are surely not too hard to find online) and read it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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