4
$\begingroup$

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.

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

$\endgroup$
2
  • $\begingroup$ Is Hall's theorem relevant here? (e.g., cs.stackexchange.com/q/103157/755, 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. $\endgroup$ – D.W. Jul 13 '20 at 5:59
  • $\begingroup$ 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... $\endgroup$ – Xin Yuan Li Jul 13 '20 at 17:02
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.