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

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.

## 1 Answer

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.

• I wonder if there is a modification to that algorithm that will find a subset S such that |N(S)| <= |S|, if one exists? Nov 7, 2023 at 0:08