Finding a subset with few neighbors
I have an idea and will be happy to know if it is correct, or can be corrected.

Consider the integer linear program:

\begin{align}
\text{maximize} &amp;&amp; \sum_{j\in Y} y_j - \sum_{i\in X} x_i
\\
\text{subject to} &amp;&amp; y_j - x_i \leq 0 &amp;&amp; \forall (i,j)\in E
\\
&amp;&amp; 0\leq x_i \leq 1,~~ 0\leq y_j \leq 1 &amp;&amp; \forall i\in X, j\in Y
\\
&amp;&amp; x_i\in \mathbb{Z},~~ y_j\in\mathbb{Z} &amp;&amp; \forall i\in X, 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 $X'$ be the subset of $X$ defined by $\{i\in X: x_i=1\}$, and $Y'$ the subset of $Y$ defined by  $\{j\in Y: y_j=1\}$.

The constraints $y_j - x_i \leq 0$ ensure that, if some vertex $j$ is in $Y'$, then all its neighbors are in $X'$, so $X'\supseteq N(Y')$.
The objective is to maximize the difference $|Y'|-|X'|$. If the optimal solution is at least 0, then $|Y'|\geq |X'| \geq |N(Y')|$, so $Y'$ is the required set. On the other hand, if the optimal solution is negative, there is no such set.

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; and if there are two nonzero entries, they have opposite signs. Therefore, we can solve the LP without the integrality constraints, and we are guaranteed to get an integral solution which gives us $Y'$.

The only problem is that the above LP does not guarantee that $Y'$ is non-empty. Adding a constraint such as $\sum_{j\in Y} y_j\geq 1$ would invalidate the argument of total-unimodularity. A possible solution is to solve $|Y|$ different linear programs: for each vertex $j\in Y$, solve the LP with the constraint $0\leq y_j \leq 1$ replaced with the constraint $y_j = 1$. If for some $j\in Y$ the objective is at least 0, we have found a non-empty $Y'$ as required. Otherwise, such $Y'$ does not exist.