patternMinor
Algorithm to find a set of nodes with a smaller set of neighbours in a bipartite graph
Viewed 0 times
nodesgraphwithneighboursbipartitealgorithmsmallerfindset
Problem
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.
This is a conceptually simple problem, but I suspect it is actually quite difficult.
Solution
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.
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.
Context
StackExchange Computer Science Q#159398, answer score: 5
Revisions (0)
No revisions yet.