Question:
In this problem, we describe a faster algorithm, due to Hopcroft and Karp, for finding a maximum matching in a bipartite graph. The algorithm runs in O($\sqrt V E$) time. Given an undirected, bipartite graph G=(V,E), where $V = L \cup R$ and all edges have exactly one endpoint in L, let M be a matching in G. We say that a simple path P in G is an augmenting path with respect to M if it starts at an unmatched vertex in L, ends at an unmatched vertex in R, and its edges belong alternately to M and E−M. (This definition of an augmenting path is related to, but different from, an augmenting path in a flow network.) In this problem, we treat a path as a sequence of edges, rather than as a sequence of vertices. A shortest augmenting path with respect to a matching M is an augmenting path with a minimum number of edges.
Given two sets A and B, the symmetric difference $ A \oplus B$ is defined as $(A – B) \cup (B – A)$, that is, the elements that are in exactly one of the two sets.
a. Show that if M is a matching and P is an augmenting path with respect to M, then the symmetric difference $M \oplus P$ is a matching and |$M \oplus P$| = |M| + 1∣. Show that if $P_1, P_2, \ldots, P_k$ are vertex-disjoint augmenting paths with respect to M, then the symmetric difference $M \oplus (P_1 \cup P_2 \cup \cdots \cup P_k)$ is a matching with cardinality |M| + k.
b. Given two matchings M and $ M^* $ in G, show that every vertex in the graph G' = (V, $ M \oplus M^* $) has degree at most 2. Conclude that G′ is a disjoint union of simple paths or cycles. Argue that edges in each such simple path or cycle belong alternately to M or $ M^* $. Prove that if |M| $ \le $ |$ M^* $|, then $ M \oplus M^* $ contains at least $ |M^*| – |M| $ vertex-disjoint augmenting paths with respect to M.
Let l be the length of a shortest augmenting path with respect to a matching M, and let $P_1, P_2, \ldots, P_k$ be a maximal set of vertex-disjoint augmenting paths of length l with respect to M. Let $M' = M \oplus (P_1 \cup \cdots \cup P_k)$, and suppose that P is a shortest augmenting path with respect to M′.
c. Show that if P is vertex-disjoint from $P_1, P_2, \ldots, P_k$, then P has more than l edges.
d. Now suppose that P is not vertex-disjoint from $P_1, P_2, \ldots, P_k$. Let A be the set of edges $(M \oplus M') \oplus P$. Show that $A = (P_1 \cup P_2 \cup \cdots \cup P_k) \oplus$ and that $|A| \ge (k + 1)l$. Conclude that P has more than l edges.
Given solution:
c. Every vertex matched by M must be incident with some edge in M'. Since P is augmenting with respect to M′, the left endpoint of the first edge of P isn't incident to a vertex touched by an edge in M′. In particular, P starts at a vertex in L which is unmatched by M since every vertex of M is incident with an edge in M'. Since P is vertex disjoint from $P_1, P_2, \ldots, P_k$ any edge of P which is in M' must in fact be in M and any edge of P which is not in M' cannot be in M. Since P has edges alternately in M' and E – M', P must in fact have edges alternately in M and E – M. Finally, the last edge of P must be incident to a vertex in R which is unmatched by M'. Any vertex unmatched by M' is also unmatched by M, so P is an augmenting path for M. P must have length at least l since l is the length of the shortest augmenting path with respect to M. If P had length exactly l, then this would contradict the fact that $P_1 \cup \cdots \cup P_k$ is a maximal set of vertex disjoint paths of length l because we could add P to the set. Thus P has more than l edges.
d. Any edge in $M \oplus M'$ is in exactly one of M or M'. Thus, the only possible contributing edges from M' are from $P_1 \cup \cdots \cup P_k$. An edge from M can contribute if and only if it is not in exactly one of M and $P_1 \cup \cdots \cup P_k$, which means it must be in both. Thus, the edges from M are redundant so $M \oplus M' = (P_1 \cup \cdots \cup P_k)$ which implies $A = (P_1 \cup \cdots \cup P_k) \oplus P$.
Now we'll show that P is edge disjoint from each $P_i$. Suppose that an edge e of P is also an edge of $P_i$ for some i. Since P is an augmenting path with respect to M' either $e \in M'$ or $e \in E – M'$. Suppose $e \in M'$. Since P is also augmenting with respect to M, we must have $e \in M$. However, if e is in M and M', then e cannot be in any of the $P_i$'s by the definition of M'. Now suppose $e \in E – M'$. Then $e \in E – M$ since P is augmenting with respect to M. Since e is an edge of $P_i$, $e \in E – M'$ implies that $e \in M$, a contradiction.
Since P has edges alternately in M' and $E – M'$ and is edge disjoint from $P_1 \cup \cdots \cup P_k$, P is also an augmenting path for M, which implies $|P| \ge l$. Since every edge in A is disjoint we conclude that $|A| \ge (k + 1)l$.
In part (d) of this problem, they assume P to be also augmented w.r.t M. How's this assumed? And after assuming this, they prove something else, and since that is proved, they say the condition they assumed earlier is true.
It seems very cyclic to me. In the previous part, they had proved that P is augmented if it is vertex disjoint. But in this part, it is not vertex disjoint.
Am I understanding wrong?
Best Answer
You are right to be suspicious - the proof is wrong. In fact, $P$ need not be edge disjoint from $P_1,\dots,P_k$, nor is it necessarily an augmenting path with respect to $M$. (And even apart from this, it is unclear how $|A| \geq (k+1)l$ would imply that the length of $P$ is strictly larger than $l$).
One way to repair this proof is the following: