In the Hopcroft-Karp algorithm for bipartite matching, I don't understand the purpose of the breadth first search. I think it's used to find a set of vertex disjoint augmenting paths, but I'm not sure what the significance of that is or even what that means. Why do the augmenting paths have to be the shortest? And why do they have to be vertex disjoint?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Vertex-disjoint means that no vertex appears in two augmenting paths. The paths have to be disjoint so that all can be used. If we have two augmenting paths, P1 and P2, and we augment the matching using using P1, is P2 still an augmenting path for the augmented matching? Yes, if P1 and P2 are vertex disjoint.
As for minimum length, it has the practical implication that we spend the shortest time looking for augmenting paths, but there is a technical matter, too. Augmenting paths found this way are guaranteed to be vertex-disjoint. Look at this text.
$\begingroup$
$\endgroup$
Why paths must be vertex disjoint? That's easy. If they are not then symmetric difference (imagine superimposing them on existing matching) might not produce new matching (i.e. one vertex might end up with two edges instead of the requirement that one vertex must have at most one edge in the matching).
Why paths needs to be shortest? My intuition is that set of shortest paths will produce biggest possible next matching. If you choose non-shortest path then we can't use any other intersecting paths with it. For shortest paths, this is minimized as much as possible so the total number of edges in all vertex disjoint paths is maximized which gives maximum possible matching for the iteration. Again, this is just my intuition, I don't have proof for this.
This answer explains choosing shortest paths n terms of greedy solution for a packing problem: https://stackoverflow.com/a/16556223/207661
