Neighborly properties in a bipartite graph

There is a polynomial time algorithm for this problem.

First, as pointed out by D.W., by Hall's theorem we can assume that there is a perfect matching between $A$ and $B$. In particular, if there is no perfect matching then there is a subset $S$ with $|S| > |N(S)|$, and we can remove vertices from $S$ without affecting $N(S)$ until we get an answer.

Now that we have a perfect matching we also have that $|S| le |N(S)|$ for any set $S$, so we are looking for a set $S$ with $|S| ge |N(S)|$.

Consider a version of this problem where we have a special vertex $a_0 in A$ and we are looking for a set $emptyset subsetneq S subseteq A setminus {a_0}$ with $|S| ge |N(S)|$. The original problem can be reduced to $|A|$ instances of this problem in polynomial time. We create a linear program that can be seen as a relaxation of this problem, and prove that this linear program has a feasible solution if and only if the problem has a solution.

The linear program has a variable $X_a ge 0$ for each vertex $a in A$ and a variable $X_b ge 0$ for each vertex $b in B$. We require that $sum_{a in A} X_a = 1$ and $sum_{b in B} X_b = 1$. For each edge $(a, b)$ we require that $X_b ge X_a$. We also set $X_{a_0} = 0$ for the special vertex $a_0$. This linear program has a feasible solution if we have a solution $S$: for each $a in S$ set $X_a = 1/|S|$ and for each $b in N(S)$ set $X_b = 1/|N(S)|$.

Let's prove that if there is a feasible solution to the linear program then we have a solution to the problem. Take $S$ as the set of vertices $a in A$ with $X_a > 0$. If $|N(S)| le |S|$ we are done. Suppose $|N(S)| > |S|$. There is a matching from $S$ to a subset $N' subsetneq N(S)$ because the graph has a perfect matching. Note that $1 = sum_{a in S} X_a le sum_{b in N'} X_b$ because the matching matches each vertex $a in S$ to a vertex $b in N'$ with $X_b ge X_a$. There is a vertex $b in (N(S) setminus N')$ with $X_b > 0$, and therefore $sum_{b in N(S)} X_b$ must be greater than $1$, which is a contradiction.