2
$\begingroup$

Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut (extracted from the final residual network) can also be used to determine the minimum vertex cover:

$$(X\cap T)\cup(Y\cap S)$$

If this expression is a correct alternative, I don't have an intuition for why it's true. The best intuition I've been able to come up with is: Select each vertex on the left (X) that has a positive flow leading up to it and select each vertex on the right if there is no flow leading up to it. Why is this set equal to the minimum vertex cover?

$\endgroup$
2
$\begingroup$

The set $(X \cap T) \cup (Y \cap S)$ is the same as the one given by the alternating path algorithm. Let $L_0,L_1,\ldots$ be the subsets considered in the alternating path algorithm (in the Wikipedia page they are called $S_0,S_1,\ldots$, but that will be confusing), and let $X_i = L_i \cap X$, $Y_i = L_i \cap Y$.

  • A vertex $x \in X_0$ is unmatched and so the edge from $s$ to $x$ is in the residual network, showing that $x \in S$. In other words, $X_0 \subseteq S$. Analogously, $Y_0 \subseteq T$.

  • A vertex $x \in X_1$ is connected to some $y \in Y_0$ via some edge not in the matching. Since $(x,y)$ is not in the matching, it belongs to the residual network. Since $y \in T$, also $x \in T$. In other words, $X_1 \subseteq T$. Analogously, $Y_1 \subseteq S$.

  • A vertex $x \in X_2$ is connected to some $y \in Y_1$ via some edge not in the matching. As before, $(x,y)$ belongs to the residual network, and so $y \in S$ implies $x \in S$. In other words, $X_2 \subseteq S$ and $Y_2 \subseteq T$.

Continuing this way, we conclude that $$ \begin{align*} S \cap X &= X_0 \cup X_2 \cup \cdots, & T \cap X &= X_1 \cup X_3 \cup \cdots, \\ S \cap Y &= Y_1 \cup Y_3 \cup \cdots, & T \cap Y &= Y_0 \cup Y_2 \cup \cdots. \\ \end{align*} $$ Therefore $$ (X \cap T) \cup (Y \cap S) = X_1 \cup X_3 \cup \cdots \cup Y_1 \cup Y_3 \cup \cdots = L_1 \cup L_3 \cup \cdots, $$ which is the output of the alternating path algorithm.

$\endgroup$
  • $\begingroup$ Thanks for the hard work you put into this answer. I still have some doubts: In your first bullet point, if I were to expand your explanation after "Analogously" in the same fashion as the first sentence in that bullet: A vertex y $\epsilon Y_0$ is unmatched and so... What comes after? Since it is unmatched it should be part of the residual network as well, but that would make it an element of S, when the conclusion is that it is an element of T :/ $\endgroup$ – Wuschelbeutel Kartoffelhuhn Apr 17 '14 at 3:31
  • $\begingroup$ @WuschelbeutelKartoffelhuhn The best way to understand this reasoning is to understand your difficulty. Therefore I suggest you work it out yourself. $\endgroup$ – Yuval Filmus Apr 17 '14 at 4:15
  • $\begingroup$ I think I got it: While the immediate predecessor arc (from an X node) is forward (unmatched), the arc in front of the predecessor (from s) cannot be forward because that X-node was matched with something else. $\endgroup$ – Wuschelbeutel Kartoffelhuhn Apr 17 '14 at 4:26
  • $\begingroup$ @WuschelbeutelKartoffelhuhn The situation is entirely symmetric. The relation of $X$-nodes to $S$ is the same as the relation of $Y$-nodes to $T$. $\endgroup$ – Yuval Filmus Apr 17 '14 at 4:29
  • $\begingroup$ Are you implying that T=V\S can also be defined to be all vertices in the residual network reachable from t? $\endgroup$ – Wuschelbeutel Kartoffelhuhn Apr 17 '14 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.