Find a minimum-cardinality Hall-violator
This is not an answer - just a long note. 

The question is related to the problem of Minimum vertex cover with minimum overlap of one side .
Suppose we have a minimum vertex cover $C$ of size $m$. By Konig's theorem, $m$ also equals the size of the maximum matching, so $m &lt; n$.

Since $C$ is a vertex cover, any vertex not in $C$ must have all its neighbors in $C$. So $N(X\setminus C)\subseteq Y\cap C$. Hence:
\begin{align}
|N(X\setminus C)| 
&amp;\leq |Y\cap C| 
\\
&amp;= m-|X\cap C| 
\\
&amp;= m-n+|X\setminus C|
\\
&amp;&lt; |X\setminus C|
\end{align}
so $X\setminus C$ is a Hall-violator. 
Now, if $X\cap C$ is large, then $X\setminus C$ is small.

However, I am not sure that finding a $C$ which maximizes $X\cap C$ also yields the smallest Hall violator.