Saturated sets in bipartite graph

Let $G=(X\cup Y, E)$ be an unweighted bipartite graph. We are given that for every $W\subseteq X$ it holds that $|W|\leq |N(W)|$, where $N(W)$ is the neighborhod of $W$ in $Y$ (aka Hall's marriage condition).

My goal is to find a subset $W^\subseteq X$ with $|W^| = |N(W^)|$, if such a subset exists (obviously it need not exist). Since I'm not aware of a formal name for this property, I'd refer to such a $W^$ as a saturated set.

Questions:

• Is this property widely known? Does it have a different name?

• Assuming the marriage condition holds, it is straightforward to show that every union of saturated sets is also saturated. One interesting problem is to find the maximum saturated set. I describe below a somewhat naive solution with runtime $O(|V|\cdot |E|)$, but I suspect it can be solved even faster. Any idea?

• Allegedly, a weakly easier problem is to find a saturated set, not necessarily the maximum one (again, assuming the marriage condition holds). Can we solve this problem faster than $O(|V|\cdot |E|)$?

Edit:
Here's a sketch for the algorithm I mentioned above: Assume the marriage condition holds for $G$. Then, as said, with a bit theory work we can show that

Lemma: Let $G$ be a bipartite graph satisfying the marriage condition. Then, every union of saturated sets is also saturated.

The Lemma suggests that there exists a unique maximum saturated set. The question can hence be stated differently:


Given a node $x\in X$, determine whether it participates in a saturated set or not.

If the answer is yes, then it also participates in the maximum saturated set. The pseudo algorithm goes as follows:

• Run the Hopcroft–Karp algorithm to find a maximal matching $M$ that covers $X$ in $O(\sqrt {|V|}|E|)$ time. Such a matching exists due to the marriage condition.

• For every node $x\in X$,

• Temporarily add a node $x'$ to $X$, which is connected to every neighbor of $x$. Call the graph we obtain $G_x$.

• Notice that $M$ is a partial matching of $

Let's fix a maximal matching $M$. Let $Z\subseteq Y$ be the set of nodes that are not matched to nodes in $X$. We can see a node $x\in X$ belongs to a saturated set if and only if there does not exist an alternating path from $x$ to a node in $Z$, i.e., a path $xy_1x_1\cdots y_kx_kz$ where $(x_i,y_i)\in M$ and $z\in Z$ (the proof is similar to the correctness proof of your algorithm).

So you can add directions to all edges in $E$ such that edges in $M$ have the direction from $X$ to $Y$ while edges not in $M$ have the direction from $Y$ to $X$, then the nodes in $X$ that are not reachable from any node in $Z$ make up the maximal saturated set. You can run a simple BFS to see which nodes in $X$ is reachable from nodes in $Z$. The time complexity is $O\left(\sqrt{|V|}|E|\right)$.

StackExchange Computer Science Q#124160, answer score: 3