We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are conected to some of the vertices from $U$. If for every choice of $U$ we have $|U| \leq |V|$ (Hall's condition) then there exists a perfect matching (Hall's theorem).
But in our graph we know there is no such matching. That means there exists some set of vertices $U$ violating Hall's condition, and I'd like to find it with complexity around $O(n^3)$ - hints instead of full solutions are most welcome.
What I already tried was finding the maximum matching first, and then searching for our subset, but I couldn't figure out how to do this. Also, I thought of ways of reducing this problem to some max-flow (as you do with the maximum matching) but it also seemed to me like a dead end.
Asked By : Cris
Answered By : Yuval Filmus
Let $G=(X,Y,E)$ be a bipartite graph with $|X|=|Y|=n$ having a maximum matching $M$. Consider the directed graph $G'$ on the vertex set $X \cup Y$ which includes the edges of $G$ oriented from $X$ to $Y$ and the edges of $M$ oriented from $Y$ to $X$. Let $U \subseteq X$ be the set of vertices of $X$ unmatched in $M$, and let $S$ be the set of vertices reachable from $U$ in $G'$. Then $|N(S \cap X)| = |S \cap X| - (n-|M|)$.
For the proof, let us first notice that $|N(S \cap X)| \geq |S \cap X| - (n-|M|)$, since otherwise each matching would have to miss more than $n-|M|$ vertices of $S \cap X$. It remains to show that $|N(S \cap X)| \leq |S \cap X| - (n-|M|)$. The idea is to show that $|X \setminus S| + |S \cap Y| \leq |M|$. Given this, note that by definition $N(S \cap X) = S \cap Y$, and so $$ |N(S \cap X)| = |S \cap Y| \leq |M| - |X \setminus S| = |M| - (n-|S \cap X|) = |S \cap X| - (n-|M|). $$
To finish the proof, we show that $|X \setminus S| + |S \cap Y| \leq |M|$. We do this by showing that each vertex in both of these sets belongs to $M$. For each $(x,y) \in M$, if $y \in S$ then $x \in S$, showing that at most one vertex is counted in $|X \setminus S| + |S \cap Y|$ for each edge in the matching, proving the inequality. It is clear that each vertex in $X \setminus S$ belongs to $M$, since by definition unmatched vertices belong to $S$. The crux of the proof is showing that each vertex in $S \cap Y$ belongs to $M$. Indeed, if some $y \in S \cap Y$ didn't belong to $M$, then the path proving that $y \in S$ is an augmenting path for the matching: if we remove all edges going from $Y$ to $X$ on the path and replace them by all edges going from $X$ to $Y$ on the path then we obtain a matching with one more edge than before. Since we assumed that $M$ is a maximum matching, this is impossible, completing the proof.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30017
0 comments:
Post a Comment
Let us know your responses and feedback