Algorithm to find a set of nodes with a smaller set of neighbours in a bipartite graph

Question

Given a bipartite graph, find a set of nodes on one side that has greater cardinality than the set of its neighbours on the other side.

This is a conceptually simple problem, but I suspect it is actually quite difficult.

Answer 1

Let $A,B$ be the two sides of the bipartite graph, we are looking for a subuset of $A$. Hall's characterization of perfect matchings states that $G$ admits a perfect matching saturating $A$ if and only if for each subset $X\subseteq A$ it holds that $|N(X)|\geq |X|$.

If the graph admits a perfect matching, then according to this theorem, no such set exists. On the other hand, if the graph does not admit a perfect matching, then a set exists, and the proof of the theorem is constructive, so you can follow it to construct such set (in linear time after finding a maximum matching). You can see a simple version of the proof here. A summary of the steps:

• Find a maximum matching $M$.

• If $M$ saturates $A$ we are done.

• Find an $M$-free vertex $v\in A$.

• Let $S$ be the set of all vertices in $A$ reachable from $v$ using $M$-alternating paths.

• $S$ is the set we are looking for.

The correctness follows fron the fact that each vertex in $N(S)$ is matched to a different vertex of $S$ (we cant visit $M$-free vertices along this process assuming $M$ is maximum, since this would imply an augmenting path from $v$). Since $S$ contains $v$ as well, it is strictly larger than $N(S)$.

For the running time you can find a maximum matching using Hopcroft and Karp‘s algorithm in time $O(\sqrt n m)$ and then build $S$ in linear time.