# Finding maximal set of vertex disjoint augmenting paths in Hopcroft Karp

In trying to implement the Hopcroft-Karp algorithm I have run into something I do not quite understand. In the step where you find the maximal set of vertex disjoint augmenting paths. How does one guarantee that you have the maximal set? Wikipedia suggests using a DFS from the unmatched verticies in one set, in the following case the lettered verticies, to the verticies that end the shortest augmenting paths in the other set, in this case 1 and 4. However, consider the following graph, which I hideously hacked together in Dia.

The edges that go from lettered nodes to numbered nodes are unmatched edges while the bold edges that go from numbered nodes to lettered nodes are currently matched edges. So now from what I understand of Wikipedia and some others (PDF) It is entirely possible in this step in the algorithm to take the path of (C,2,A,1) as the only augmenting path if you start with C and choose poorly. When obviously the right maximal set of disjoint shortest augmenting paths are (B,2,A,1) and (C,3,D,4). So How do you guarantee a maximal set of augmenting paths? Kudos also if you have a better idea for drawing graphs than Dia.

-
Wow. It only needs to be a maximal set, rather than a maximum set. Totally missed that. So my question is moot. – janders Nov 20 '11 at 19:57