# Find a minimum-cardinality Hall-violator

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?

• It is also interesting to find a maximum-cardinality Hall-violator. Jan 16 '19 at 7:32
• 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. Jan 17 '19 at 17:22
• 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. Jan 17 '19 at 17:34
• Some related problems are mentioned here en.wikipedia.org/wiki/Hall_violator Dec 10 '21 at 11:59

This is not an answer but a collection of notes.

## ILP formulation

Consider the following integer linear program:

\begin{align} \text{minimize} && \sum_{i\in X} x_i \\ \text{subject to} && y_j - x_i \geq 0 && \forall (i,j)\in E \\ && \sum_{i\in X} x_i - \sum_{j\in Y} y_j \geq 1 \\ && x_i\in\{0,1\} && \forall i\in X \\ && y_j\in\{0,1\} && \forall j\in Y \end{align} In this program, there is a variable $$x_i$$ for each node $$i$$ in $$X$$, and a variable $$y_j$$ for each node $$j$$ in $$Y$$. Let $$S$$ be the subset of $$X$$ defined by $$\{i\in X: x_i=1\}$$, and $$T$$ the subset of $$Y$$ defined by $$\{j\in Y: y_j=1\}$$.

First, we show that every feasible solution corresponds to a Hall violator:

• The constraints $$y_j -x_i \geq 0$$ ensure that, if some vertex $$i$$ is in $$S$$, then all its neighbors are in $$T$$, so $$T\supseteq N(S)$$.
• The constraint $$\sum_{i\in X} x_i - \sum_{j\in Y} y_j \geq 1$$ guarantee that $$|S| > |T|$$, so $$|S| > N(S)$$ and $$S$$ is a Hall violator.

Next, we show that every Hall violator corresponds to a feasible solution. Indeed, if $$S$$ is a Hall violator, then taking $$T = N(S)$$ yields a feasible solution.

Therefore, minimizing $$|S|$$ yields a minimum-cardinality Hall violator.

In general, integer programs are NP-hard, but maybe this specific program can be solved efficiently?

## Inclusion-minimal Hall violator

there is a polynomial-time algorithm for a closely-related problem: finding a minimal Hall violator (one that does not contain a smaller Hall violaor). It is described in Lemma 2.1 of following paper:

Gan, Suksompong and Voudouris: Envy-freeness in house allocation problems, Mathematical Social Sciences, 2019.

## Relation to vertex cover

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.

This problem is $$\mathsf{NP}$$-hard. The problem is also known as Hall set problem and there is a reduction from Clique problem. See Theorem 3.2.5 from this thesis.

I was thinking along the direction of the Minimum $$k$$-Union problem. Then, I came across this thesis.

• Thanks a lot! Indeed, in this thesis, a Hall violator is defined as a Hall set. And the "Hall Set Problem" is the following problem: "In a bipartite graph G with bipartite classes (A, B) and given a positive integer k, does there exists a Hall Set of size at most k?". Theorem 3.2.5 says "Theorem 3.2.5. [4] There is a parameterized reduction from Clique to Hall Set on general bipartite graph." They link to "[4] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dniel Marx, Marcin Pilipczuk, Micha Pilipczuk and Saket Saurabh, Parameterized Algorithms, Springer, 2016." Dec 17 '21 at 9:29
• @ErelSegal-Halevi In the book, it is given as Exercise 13.28. Dec 17 '21 at 9:38

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.

• 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$. Jun 4 '19 at 13:49
• 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$. Jun 4 '19 at 13:50
• @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.
– mhum
Jun 5 '19 at 2:43
• regarding the first comment: indeed I did not notice that $v_2$ is in $Y$, thanks for the clarification. Jun 5 '19 at 4:56
• @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.
– mhum
Jun 13 '19 at 1:28