<p>There is a polynomial time algorithm for this problem.</p>
<p>First, as pointed out by D.W., by Hall's theorem we can assume that there is a perfect matching between <span class="math-container">$A$</span> and <span class="math-container">$B$</span>.
In particular, if there is no perfect matching then there is a subset <span class="math-container">$S$</span> with <span class="math-container">$|S| &gt; |N(S)|$</span>, and we can remove vertices from <span class="math-container">$S$</span> without affecting <span class="math-container">$N(S)$</span> until we get an answer.</p>
<p>Now that we have a perfect matching we also have that <span class="math-container">$|S| \le |N(S)|$</span> for any set <span class="math-container">$S$</span>, so we are looking for a set <span class="math-container">$S$</span> with <span class="math-container">$|S| \ge |N(S)|$</span>.</p>
<p>Consider a version of this problem where we have a special vertex <span class="math-container">$a_0 \in A$</span> and we are looking for a set <span class="math-container">$\emptyset \subsetneq S \subseteq A \setminus \{a_0\}$</span> with <span class="math-container">$|S| \ge |N(S)|$</span>. The original problem can be reduced to <span class="math-container">$|A|$</span> 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.</p>
<p>The linear program has a variable <span class="math-container">$X_a \ge 0$</span> for each vertex <span class="math-container">$a \in A$</span> and a variable <span class="math-container">$X_b \ge 0$</span> for each vertex <span class="math-container">$b \in B$</span>.
We require that <span class="math-container">$\sum_{a \in A} X_a = 1$</span> and <span class="math-container">$\sum_{b \in B} X_b = 1$</span>. For each edge <span class="math-container">$(a, b)$</span> we require that <span class="math-container">$X_b \ge X_a$</span>. We also set <span class="math-container">$X_{a_0} = 0$</span> for the special vertex <span class="math-container">$a_0$</span>. This linear program has a feasible solution if we have a solution <span class="math-container">$S$</span>: for each <span class="math-container">$a \in S$</span> set <span class="math-container">$X_a = 1/|S|$</span> and for each <span class="math-container">$b \in N(S)$</span> set <span class="math-container">$X_b = 1/|N(S)|$</span>.</p>
<p>Let's prove that if there is a feasible solution to the linear program then we have a solution to the problem.
Take <span class="math-container">$S$</span> as the set of vertices <span class="math-container">$a \in A$</span> with <span class="math-container">$X_a &gt; 0$</span>. If <span class="math-container">$|N(S)| \le |S|$</span> we are done.
Suppose <span class="math-container">$|N(S)| &gt; |S|$</span>.
There is a matching from <span class="math-container">$S$</span> to a subset <span class="math-container">$N' \subsetneq N(S)$</span> because the graph has a perfect matching.
Note that <span class="math-container">$1 = \sum_{a \in S} X_a \le \sum_{b \in N'} X_b$</span> because the matching matches each vertex <span class="math-container">$a \in S$</span> to a vertex <span class="math-container">$b \in N'$</span> with <span class="math-container">$X_b \ge X_a$</span>.
There is a vertex <span class="math-container">$b \in (N(S) \setminus N')$</span> with <span class="math-container">$X_b &gt; 0$</span>, and therefore <span class="math-container">$\sum_{b \in N(S)} X_b$</span> must be greater than <span class="math-container">$1$</span>, which is a contradiction.</p>

CC BY-SA 4.0
2020-07-13T19:35:16.277Z
2020-07-13T20:30:34.377Z
2020-07-13T20:30:34.377Z
Laakeri
<p><strong>Input:</strong> Let <span class="math-container">$G$</span> be a connected, bipartite graph with parts <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, each of size <span class="math-container">$n$</span>. For a set of vertices <span class="math-container">$S$</span>, let <span class="math-container">$N(S)$</span> be its set of neighbors.</p>
<p><strong>Question:</strong> Decide whether there exists a subset <span class="math-container">$S\subseteq A$</span> with <span class="math-container">$\emptyset\ne S\ne A$</span> such that <span class="math-container">$|S|=|N(S)|$</span>.</p>
<p><strong>My attempts so far:</strong> First some observations. If <span class="math-container">$a \in A$</span> has <span class="math-container">$\deg(a) = 1$</span>, then we are done so it suffices to consider the case where <span class="math-container">$\deg(a)\ge2$</span> for all <span class="math-container">$a\in A$</span>. Further, if we can find a proper subset <span class="math-container">$S\subseteq A$</span> such that <span class="math-container">$|S|\ge|N(S)|$</span> then we are also done (remove a well chosen vertex of <span class="math-container">$S$</span> one at a time). The problem is straight-forward to solve if <span class="math-container">$G$</span> is a tree.</p>
<p>Various greedy approaches have been tried and have thus far failed e.g. consider the following counter-example for greedy by smallest degree.</p>
<p><a href="https://i.sstatic.net/KxtOQ.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/KxtOQ.jpg" alt="Greedy by minimum degree counter-example." /></a></p>
<p>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).</p>

CC BY-SA 4.0
2020-07-13T05:59:02.507Z
Is Hall's theorem relevant here?  (e.g., https://cs.stackexchange.com/q/103157/755, https://cs.stackexchange.com/q/30017/755) - I don't see any way to apply this directly, but maybe you will see something I'm missing.
D.W.
CC BY-SA 4.0
2020-07-13T17:02:10.500Z
Thanks, for the links! They were quite useful! The general idea is to find a  maximum matching $M$ in the bipartite graph. Either $M$ is a perfect matching or it is not. In the latter case, we can combine the result of your second link and the second observation (under my attempts) to come up with an appropriate $S$. I still need to think about the case where $M$ is a perfect matching...
Xin Yuan Li
<graph-theory><graph-algorithms><np-hardness>
Neighborly properties in a bipartite graph
Xin Yuan Li
# Neighborly properties in a bipartite graph

(Asked by: username_0 on 2020-07-12)

**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.

[![Greedy by minimum degree counter-example.](https://i.sstatic.net/KxtOQ.jpg)](https://i.sstatic.net/KxtOQ.jpg)

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).

**Tags:** graph-theory, graph-algorithms, np-hardness

> **Comments:**
> **username_1**: Is Hall's theorem relevant here?  (e.g., https://cs.stackexchange.com/q/103157/755, https://cs.stackexchange.com/q/30017/755) - I don't see any way to apply this directly, but maybe you will see something I'm missing.  
> **username_0**: Thanks, for the links! They were quite useful! The general idea is to find a  maximum matching $M$ in the bipartite graph. Either $M$ is a perfect matching or it is not. In the latter case, we can combine the result of your second link and the second observation (under my attempts) to come up with an appropriate $S$. I still need to think about the case where $M$ is a perfect matching...  

---

## 1 answers

### Answer by username_2 on 2020-07-13. Score: 1 | Accepted answer

There is a polynomial time algorithm for this problem.

First, as pointed out by username_1, 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.


---

