5
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Can you describe your $O(|V||E|)$ algorithm? Does it use the Hall property somehow? I don't yet see a way to avoid considering all subsets of at least one of the sides, leading to an exponential-time algorithm. $\endgroup$ – j_random_hacker Apr 16 at 12:48
  • $\begingroup$ If a perfect matching exists, this is a maximum-size saturated set. $\endgroup$ – j_random_hacker Apr 16 at 12:53
  • $\begingroup$ (So, since we are already told that Hall's condition holds, if $|X|=|Y|$ then a perfect matching exists and the maximum-size saturated set is $X$ itself.) $\endgroup$ – j_random_hacker Apr 16 at 13:04
  • $\begingroup$ Added the algorithm, would appreciate comments. Indeed, if $|X|=|Y|$ the problem becomes trivial. $\endgroup$ – omerbp Apr 16 at 21:34
  • 1
    $\begingroup$ I took a quick look at Lovász and Plummer ("Matching theory") and couldn't find anything relevant, but perhaps it warrants a second look. Another relevant resource is Schrijver ("Combinatorial optimization"). The closest concept I can think of is Hall violator, which are sets violating Hall's condition. $\endgroup$ – Yuval Filmus Apr 17 at 7:48
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Trying to understand your definition of "alternating path": The "i.e." part does not say anything about the edges $(x_i, y_{i+1})$, but since you call it an alternating path, I presume these must be absent from $M$? But in that case any such path is in fact an augmenting path, so if we then choose $M$ to be maximum (and not merely maximal), no such path exists, so we can conclude that every vertex belongs to a saturated set, which is incorrect. What am I missing? $\endgroup$ – j_random_hacker Apr 17 at 12:59
  • 1
    $\begingroup$ @j_random_hacker If $(x_i,y_{i+1})\in M$ then $y_{i+1}=y_i$, which is meaningless but there is no problem if we allow it, so I don't write any constraint on $(x_i,y_{i+1})$. This is not an augmenting path because one of the endpoints $x$ is matched. $\endgroup$ – xskxzr Apr 17 at 13:07
  • $\begingroup$ Of course, $x$ is already matched, so the path is not an augmenting path. And $M$ being a matching forbids adjacent edges. Thanks! $\endgroup$ – j_random_hacker Apr 17 at 13:09
  • $\begingroup$ @xskxzr Thanks, this your answer seems to solve the problem. One comment: Your solution still requires a maximal matching $M$, so technically the time complexity is $O(\sqrt {|V|} |E|)$, right? $\endgroup$ – omerbp Apr 17 at 14:32
  • $\begingroup$ @omerbp Yes, I have corrected it. $\endgroup$ – xskxzr Apr 17 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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