Saturated sets in bipartite graph

Question

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:

1. Is this property widely known? Does it have a different name?
2. 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?
3. 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:

1. 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.
2. 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 $G_x$ that is almost maximal (up to one edge); thus, we can find a maximal matching $M_x$ for $G_x$ by finding an augmenting path in $G_x$, in $O(|V|+|E|)$ time (same details as in Hopcroft–Karp).
   • If $|M|<|M_x|,$ continue. Else, if $|M|=|M_x|$, add $x$ to the returned set.

The analysis follows from first principles. If there exists any saturated set $W\subseteq X$ with $x\in W$, i.e., $|W|=|N_G(W)|$ then $$ |W\cup \{x'\}|=|W|+1 = |N_G(W)|+1=|N_{G_x}(W)|+1, $$ so $W\cup \{x'\}$ violates the marriage condition in $G_x$. Consequently, $|M|=|M_x|$. We can analogously show that if $x$ does not participate in any saturated set, then $|M_x|=|M|+1$.

Answer 1

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)$.