1
$\begingroup$

Source

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?

$\endgroup$
4
  • $\begingroup$ @bof Fair enough. I have added the question to the body. I apologize for the earlier external site redirection. $\endgroup$ Sep 5, 2020 at 7:49
  • $\begingroup$ Good. I've edited to mark the quoted block clearly. Please fix if I have messed anything up. Now you also need to identify the source that you are quoting from, since unattributed quotations are frowned upon. As for answering your question, I think I'd better leave that to our resident graph theory experts. $\endgroup$
    – bof
    Sep 5, 2020 at 10:09
  • $\begingroup$ What is "ppp" on the first line of the quote? Is that an abbreviation or a typo? $\endgroup$
    – bof
    Sep 5, 2020 at 10:11
  • $\begingroup$ Thanks for the edits, and yes that was a typo. The first line has a hyperlink to the original source. Is there some other way to cite? $\endgroup$ Sep 5, 2020 at 11:33

1 Answer 1

0
$\begingroup$

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:

  1. Show that if $P$ is edge disjoint from $P_1,\dots,P_k$, then it is also vertex disjoint from them, so by our assumption it must be longer than $l$, as detailed in part c.
  2. Show that if $P$ is not edge disjoint from $P_1,\dots,P_k$, then it must be longer than $l$, for otherwise there would be an augmenting path $P'$ with respect to $M$ that is shorter than $l$.
$\endgroup$
7
  • $\begingroup$ Thanks for clearing it up. In the 2nd part however, would it be necessarily true? If P is not edge disjoint, shorter than L, and has the first edge from M (which is also in the P union). This would be possible since the first edge needs to be E - M', and M' excludes the edges in M that are in the maximal shortest augmenting paths w.r.t M set (the P union). $\endgroup$ Sep 6, 2020 at 14:14
  • $\begingroup$ When you add (or, rather, "switch along") the augmenting paths to obtain $M'$ from $M$, the set of points covered by the matching strictly increases. So a vertex that is unmatched by $M'$ is unmatched by $M$ as well. In particular, an augmenting path w.r.t. $M'$ cannot start with an edge from $M$. $\endgroup$
    – Dániel G.
    Sep 6, 2020 at 14:53
  • $\begingroup$ You're right, I didn't catch that. However, the next edge will be from M', which can include a subset from E - M right (since those would be the edges left from the P union after the symmetric difference). Since the only constraint is that the matched vertices be the same, but they can be matched by different edges in M and M'. So in case it has an edge from E - M, then another edge from E - M and another edge from M (Since we no longer have the matching constraint, in which case we can use any edge from E - M' which includes some edges in M). It would no longer be an augmenting path? $\endgroup$ Sep 6, 2020 at 16:56
  • $\begingroup$ I'm not sure what is it that you're asking. What would no longer be an augmenting path? $\endgroup$
    – Dániel G.
    Sep 6, 2020 at 17:40
  • $\begingroup$ I was talking about P, that it can have edges belonging to E-M, E-M and M in that order, and it'll still be augmenting w.r.t M'. However, it would not be augmenting with respect to M. $\endgroup$ Sep 6, 2020 at 18:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .