World's most popular travel blog for travel bloggers.

[Solved]: Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths

, , No Comments
Problem Detail: 

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?

Asked By : Wuschelbeutel Kartoffelhuhn

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback