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| &gt; |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 &gt; 0$. If $|N(S)| \le |S|$ we are done.
Suppose $|N(S)| &gt; |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 &gt; 0$, and therefore $\sum_{b \in N(S)} X_b$ must be greater than $1$, which is a contradiction.