4
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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