Augmenting Path Algorithm - Maximum Matching

Question

I was reading the augmenting path or Kuhn's algorithm to find the maximum matching size in an unweighed bipartite graph.

The algorithm tries to find an alternating path(consisting of alternating unmatched and matched edges) starting and ending at unmatched vertices. If an alternating path is found, the path is augmented and matching count is increased by 1.

I can understand the algorithm, however I have problem in understanding the way it is generally implemented. Here is a reference implementation - https://sites.google.com/site/indy256/algo/kuhn_matching2 .

At each stage, we should try to find an alternating path beginning from an unmatched vertex on the left. However, in the given implementation, in each iteration, instead of trying all unmatched vertices as possible start locations, we instead start our search from only a single unmatched vertex, as shown in the following code -

for (int u = 0; u < n1; u++) {
      if (findPath(graph, u, matching, new boolean[n1]))
        ++matches;
    }

This way, a vertex on left, which is not matched during its iteration, is never tried again. I can't understand why is this optimal?

BlinkingStar BlinkingStar · Accepted Answer · 2016-12-08T15:49:44

It's sufficient to prove there will be no augment path left after algorithm ends. Since no augment path means max flow. Let's say A[i] as left i'th vertices, and B[i] right i'th vertices.

If A[i] has been matched, then it will remain matched in any augmenting path.

So, our only concern is when we've considered A[i] and found no match but after some iterations in for loop, A[i] suddenly has new augment path. We will show it'll never happen.

Let's consider A[i] has no augmenting path before and say S as set of vertices which can be visited by dfs(i). There are only 2 ways for new vertices(which was not in S before) to be included in S afterwards.

For some A[x] in S, edge A[x] - B[y] is changed from matched to unmatched (B[y] will be included in S afterwards)

Contradiction. Because we should find augmenting path B[y] - A[x] - ... - Sink, but Sink is not in S so we can't do that.
For some B[y] in S, edge B[y] - A[x] is changed from unmatched to matched (A[x] will be included in S afterwards)

Contradiction again. This time, we should find augmenting path A[x] - B[y] - ... - Sink, but again, we can't reach to Sink from B[y].

For the reasons above, it is impossible to accidentally left augmenting path which implies maximum flow.

Augmenting Path Algorithm - Maximum Matching

2 Answers