7
$\begingroup$

Given a bipartite graph $(X,Y,E)$, in which there is no perfect matching, I want to find a smallest subset that violates Hall's condition, i.e., a minimum-cardinality set $S \subseteq X$ for which $|N(S)|<|S|$.

This problem is the optimization version of a former question Finding a subset in bipartite graph violating Hall's condition, from which I know there exists a polynomial-time algorithm for finding such $S \subseteq X$. Does there exists a polynomial algorithm for the optimization problem?

$\endgroup$
  • $\begingroup$ It is also interesting to find a maximum-cardinality Hall-violator. $\endgroup$ – Erel Segal-Halevi Jan 16 at 7:32
  • 2
    $\begingroup$ It is also interesting to find one of the most violating Hall-violators, that is, $S \subseteq X$ for which $|S|-|N(S)|$ takes maximum value. $\endgroup$ – Apass.Jack Jan 17 at 17:22
  • $\begingroup$ It might be the most interesting to find a set of edges with the least cardinality or just the least cardinality such that once those edges are added, a perfect matching is possible. $\endgroup$ – Apass.Jack Jan 17 at 17:34
2
$\begingroup$

This is not an answer - just a long note.

The question is related to the problem of Minimum vertex cover with minimum overlap of one side . Suppose we have a minimum vertex cover $C$ of size $m$. By Konig's theorem, $m$ also equals the size of the maximum matching, so $m < n$.

Since $C$ is a vertex cover, any vertex not in $C$ must have all its neighbors in $C$. So $N(X\setminus C)\subseteq Y\cap C$. Hence: \begin{align} |N(X\setminus C)| &\leq |Y\cap C| \\ &= m-|X\cap C| \\ &= m-n+|X\setminus C| \\ &< |X\setminus C| \end{align} so $X\setminus C$ is a Hall-violator. Now, if $X\cap C$ is large, then $X\setminus C$ is small.

However, I am not sure that finding a $C$ which maximizes $X\cap C$ also yields the smallest Hall violator.

$\endgroup$
1
$\begingroup$

tl;dr: I've found a fatal gap in this proof that I've been unable to close. I'll leave this answer up in case either: a) I figure out how to fix it or b) it inspires someone else to figure out how to fix it.


Let $G = (X \cup Y, E)$ be a bipartite graph without a perfect matching. We'll say that a subset $S$ is deficient if $|N(S)| \lt |S|$. We are looking for a minimum, deficient subset of $X$. The general approach will be to identify potential minimum, deficient sets by characterizing (and finding) all the minimal, deficient sets, i.e.: deficient sets $S\subset X$ that contains no deficient subsets. Let's make a few observations on the properties of these minimal, deficient sets.

Observation 1: A subset $S$ is a minimal deficient subset of $X$ iff for all $s \in S$, the set $S\setminus \{s\}$ has a perfect matching in $G$. This is just Hall's Theorem.

Observation 2: If $S$ is a minimal deficient subset of $X$, then for all $s_1, s_2 \in S$, there exists a path in $G$ from $s_1$ to $s_2$. Otherwise, we could decompose $S$ into two (or more) components, at least one of which would have to be deficient, thus contradicting minimality.

Now, let us fix $M$, some maximum matching in $G$. Let $X' \subset X$ and $Y' \subset Y$ be the vertices that are matched by $M$ and let $U = X\setminus X'$ be the subset of unmatched vertices in $X$. For any subset $S$ of $X$, we will also denote $m(S)$ as the set of vertices in $G$ reachable from $S$ via $M$-alternating paths.

In an answer to the question linked in the OP, we see a proof that if we take $S = U \cup (m(U) \cap X)$ then $S$ is deficient. Careful reading of that proof reveals that it works not just for $U$ but any subset of $U$. That is to say, if we take any subset $U_1 \subseteq U$, then $U_1 \cup (m(U_1) \cap X)$ is a deficient subset of $X$. In particular, we may take $U_1$ to be a singleton set. For any $u \in U$, let's define $D_u = \{u\} \cup (m(\{u\}) \cap X)$.

Lemma 1: $D_u$ is a minimal, deficient set for all $u \in U$.

Proof: We'll take for granted that $D_u$ is deficient via proof given in the previously referenced answer. To show that $D_u$ is minimal w.r.t. deficiency, we observe that $D_u \setminus \{u\}$ is simply a subset of $X'$, hence there exists a perfect matching for it inside of $G$ (just take the restriction of $M$ to $D_u\setminus \{u\}$). For any other $y \in D_u$, we follow the $M$-alternating path from $y$ to $u$, flip all the edges along this path, and obtain a perfect matching of $D_u \setminus \{y\}$ in $G$. So, by Observation 1, $D_u$ is a minimal, deficient set. $\square$

Ok, now that we've identified one collection of minimal, deficient subsets of $X$, we need to ask: what about any others?

To add a little structure, let us consider any set $S \subseteq X$ to be in the form $S = U_1 \cup Z_1 \cup Z_2$ where $U_1 \subseteq U$, $Z_1 \subseteq m(U_1)$ and $Z_2 \subseteq X' \setminus m(U_1)$. In other words, we break $S$ into the portion that's unmatched by $M$ ($U_1$), the portion that's reachable from $U_1$ via $M$-alternating paths ($Z_1$), and the portion that's not reachable from $U_1$ via $M$-alternating paths ($Z_2$). It's trivial to observe that if $S$ is a deficient set, then $U_1$ must be non-empty.

Via Lemma 1, we have covered the case where $Z_1 = m(U_1)$ and $Z_2$ is empty. This leaves three cases to examine:

  1. $Z_2$ is non-empty
  2. $|U_1| > 1$ and $Z_1 \subsetneq m(U_1)$
  3. $Z_1$ and $Z_2$ are both empty (i.e.: $S \subseteq U$).

Lemma 2: If $S = U_1 \cup Z_1 \cup Z_2 \subseteq X$ is such that $Z_2 \neq \emptyset$, then $S$ is not a minimal, deficient subset of $X$.

Proof: Let $M(Z_2)$ be the elements of $Y$ that are matched with $Z_2$ in $M$. By definition, there can be no edges from $U_1$ nor $Z_1$ to $M(Z_2)$ since that would imply an $M$-alternating path from $U_1$ to vertices in $Z_2$.

If $S$ is a minimal, deficient set, then every subset of $S$ has a complete matching. In particular, $U_1 \cup Z_1$ has a complete matching, say $M_1$. By our previous observation, we note that this complete matching $M_1$ does not use any of the vertices in $M(Z_2)$. Thus, the matching formed by using $M_1$ to match $U_1 \cup Z_1$ and $M$ to match $Z_2$ is a complete matching for $S$, contradicting the assumption that $S$ was deficient. $\square$

In a previous version of this answer, I had neglected case 2), assuming that it was somehow covered during the proof of Lemma 1. However, this is not the case. There can exist minimal, deficient sets which do not look like $D_u$. The following diagram shows such an example. Taking the bolded edges as the matching $M$, we can see that $S = \{A, B, C\}$ is a minimal, deficient set and is not of the form $D_u$. I haven't yet been able to find an effective characterization of minimal deficient sets that fall into case 2, so I am currently unable to complete this proof.

enter image description here

$\endgroup$
  • $\begingroup$ I noticed this beautiful answer just now. A question for clarification: can "M-alternating path" have a single edge? It seems that any single edge, whether in M or not, is technically "M-alternating". If so, then case 1 of lemma 2 can be made much shorter: if $v_2$ is unmatched by $M$, then it is in $U_1$; there is a single edge between it and $z$, so $z$ is accessible from $U_1$. $\endgroup$ – Erel Segal-Halevi Jun 4 at 13:49
  • $\begingroup$ On the other hand, I did not understand case 2 of Lemma 2: what if we have $z, v_2, v_3$ all matched by $M$, but in the path they are linked by edges not in $M$? Then, we can have an M-alternating path from $v_2$ to $u$, but it does not extend to an M-alternating path from $z$ to $u$. $\endgroup$ – Erel Segal-Halevi Jun 4 at 13:50
  • $\begingroup$ @ErelSegal-Halevi Regarding your first comment, I'm not sure I fully understand. $v_2$ would have to be an element of $Y$ so it cannot be in $U_1$ and there is not necessarily an edge between $v_2$ and $U_1$. As for your second comment, I think you have a point. I've been unable to reproduce that part of the proof. I will need to rethink this part and see if I can salvage it. $\endgroup$ – mhum Jun 5 at 2:43
  • $\begingroup$ regarding the first comment: indeed I did not notice that $v_2$ is in $Y$, thanks for the clarification. $\endgroup$ – Erel Segal-Halevi Jun 5 at 4:56
  • 1
    $\begingroup$ @ErelSegal-Halevi I have good news and bad news. The good news is that I was able to repair the gap in the proof that you identified with a much simpler observation. The bad news is that in reviewing my work I found a much, much bigger problem that I have not been able to fix yet. $\endgroup$ – mhum Jun 13 at 1:28

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.