Find a minimum-cardinality Hall-violator

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.