Finding the set that violates Hall’s condition in a bipartite graph.

Question

If I have a bipartite graph for which it is given that there does not exist any complete matching. This implies that Hall’s condition is not satisfied for this graph. So, there must be atleast one set $S$, such that $|S|>|N(S)|$. I want a way to find this set. The only thing I can think of is eventually just checking for all the subsets. I would greatly appreciate any help in finding such a set more efficiently. Thanks!

Answer 1

Let $G(A, B, E)$ be your bipartite graph.

You can solve the maximum matching problem on this graph. Let $C$ be the set of vertices reachable by an augmenting path from an unmatched vertex of $A$. You can set $S = C\cap A$.

See https://en.wikipedia.org/wiki/Hall_violator for more details

Answer 2

You can solve the problem via integer linear programming as follows. For $a\in A$, let binary decision variable $x_a$ indicate whether $a\in S$. For $b\in B$, let binary decision variable $y_b$ indicate whether $b\in N(S)$. The problem is to maximize $\sum_a x_a - \sum_b y_b$ subject to $x_a \le y_b$ for all $a\in A$ and $b\in N_a$. If the resulting objective value is positive, then $S=\{a\in A: x_a = 1\}$ provides the desired certificate.