Neighborly properties in a bipartite graph

Question

Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For a set of vertices $S$, let $N(S)$ be its set of neighbors.

Question: Decide whether there exists a subset $S\subseteq A$ with $\emptyset\ne S\ne A$ such that $|S|=|N(S)|$.

My attempts so far: First some observations. If $a \in A$ has $\deg(a) = 1$, then we are done so it suffices to consider the case where $\deg(a)\ge2$ for all $a\in A$. Further, if we can find a proper subset $S\subseteq A$ such that $|S|\ge|N(S)|$ then we are also done (remove a well chosen vertex of $S$ one at a time). The problem is straight-forward to solve if $G$ is a tree.

Various greedy approaches have been tried and have thus far failed e.g. consider the following counter-example for greedy by smallest degree.

I am beginning to suspect that the problem is NP-hard, but I do not have any good reduction sources (Hamilton Cycle comes to mind, but that uses all the vertices of the graph).

Answer 1

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.