Given a bipartite graph $G(X+Y,E)$, how can I find a non-empty subset $Y'\subseteq Y$, such that $|N(Y')| \leq |Y'|$ (where $N$ is the set of neighbors)?
If $|Y|\geq |X|$ then the problem is easy - $Y'=Y$ satisfies the requirements. The interesting case is $|Y| < |X|$. In this case a solution might not exist, for example here:
$$ x_1 - y_1 \\ x_2 - y_1 $$
the only subset of $Y$ that satisfies the requirement is $\emptyset$. Is there an efficient algorithm for deciding whether a solution exists, and if so, find one?
A possible first step is to find a maximum matching in the graph. If its size is less than $|Y|$, then by Hall's theorem there exists a $Y'\subseteq Y$ with $|N(Y')|< |Y'|$, and it can be found efficiently, so we are done.
But if the size of the matching is $|Y|$, then... I am stuck.
RELATED PROBLEMS:
Finding a subset in bipartite graph violating Hall's condition: there, the problem is to find a subset with $|N(Y')|< |Y'|$; here, the problem is to find a non-empty subset with $|N(Y')|\leq |Y'|$.
In bipartite expansion, the goal is to find a subset $Y'$ containing a fraction $\beta$ of the vertices of $Y$ which minimizes the size of $N(Y')$. The problem is hard to approximate. However, our problem is possibly easier, since we only require $Y'$ to be non-empty, and only require $|N(Y')|$ to be at most $|Y'|$ - we do not try to minimize it.
In union minimization, we are given a set-system and an integer $k$, and the goal is to find $k$ sets such that their union is minimized. We can view the set-system as a bipartite graph with sets on one side and elements on the other side; then, the goal is to find a $Y'$ of size $k$, such that $|N(Y')|$ is minimized. This is hard to approximate, but again our problem is potentially easier since it does not insist on $k$ and does not require minimization.
So, can the problem be solved in polynomial time?