Finding a subset in bipartite graph violating Hall's condition

Question

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.

Answer 1

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.

Answer 2

Here is an alternative answer. I will be happy to know if it is correct.

Let the bipartite graph be $(X+ Y, E)$. Consider the integer linear program:

\begin{align} \text{maximize} && \sum_{i\in X} x_i - \sum_{j\in Y} y_j \\ \text{subject to} && x_i - y_j \leq 0 && \forall (i,j)\in E \\ && x_i\in\{0,1\} && \forall i\in X \\ && y_j\in\{0,1\} && \forall j\in Y \end{align} In this program, there is a variable $x_i$ for each node $i$ in $X$, and a variable $y_j$ for each node $j$ in $Y$. Let $S$ be the subset of $X$ defined by $\{i\in X: x_i=1\}$, and $T$ the subset of $Y$ defined by $\{j\in Y: y_j=1\}$.

The constraints $x_i - y_j \leq 0$ ensure that, if some vertex $i$ is in $S$, then all its neighbors are in $T$, so $T\supseteq N(S)$. The objective is to maximize the difference $|S|-|T|$. If the objective is positive, then $|S|>|T| \geq |N(S)|$, so $S$ is the Hall violator that we are looking for; otherwise, there is no Hall violator.

In general, integer linear programs are hard to solve. But in this case, the matrix of constraints is Totally unimodular. It satisfies the Hoffman-Gale conditions:

• Every entry in the matrix is one of $+1, 0, -1$;
• Every row in the matrix contains at most two nonzero entries.
• In every row, there are no two nonzero entries with the same sign: every row contains exactly one $+1$ and one $-1$ and the rest are zeros.

Therefore, the LP relaxation of this ILP has an integral solution. So we can solve this LP in polynomial time and use the solution to construct the Hall-violator $S$.

Is this algorithm correct?