Either find a perfect matching, or return a witness that none exist [duplicate]

Question

I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options:

1. If a perfect matching exists, it returns the matching;

2. Otherwise, it returns a witness based on Hall's theorem, i.e., a set $S\subseteq X$ such that the number of neighbors of $S$ is smaller than $|S|$.

I found in wikipedia various algorithms for finding a maximum matching in an unweighted bipartite graph. Such algorithms can be used to determine if a perfect matching exists. But does any of these algorithms also return an evidence in case of failure?

EDIT: I have read the links in the answer of Yuval Filmus below, but it took me some time to fill in the missing details. For future reference, here is a detailed solution. Below, let $n := |X| = |Y|$.

Step 1. Define a flow network with $2n+2$ nodes in the following structure:

$$ s \rightrightarrows X \rightrightarrows Y \rightrightarrows t $$

where:

• $s$ is a new source node connected to all vertices in $X$ with capacity 1;
• every original edge of $E$ is directed from $X$ to $Y$ with capacity $\infty$;
• each vertex in $Y$ is connected with capacity 1 to a new sink node $t$.

Step 2. Use the Ford-Fulkerson algorithm to find a maximum flow in that graph. Suppose the maximum flow size is $m$ (which must be at most $n$).

Step 3. If $m = n$ then we are done - the flow induces a matching of size $n$ which is perfect.

Step 4. Otherwise, $m < n$. The FF algorithm also returns an $s$-$t$ minimum cut of size $m$ - a partition $(C,C')$ of the vertices in the graph, such that $s\in C$, $t\in C'$, and the sum of capacities of edges directed from $C$ to $C'$ is $m$.

This cut cannot cross any edge of $E$, since these edges have infinite capacity. Hence, the cut size is determined by edges from $s$ to $X\cap C'$ and from $Y\cap C$ to $t$. So $m = |X\cap C'| + |Y\cap C| = (n-|X\cap C|)+|Y\cap C|$. Hence: $|X\cap C| = |Y\cap C| + (n-m) > |Y\cap C|$. Since the cut cannot cross edges of $E$, all neighbors of $|X\cap C|$ must be in $|Y\cap C|$, so $|X\cap C|$ is the desired Hall-violator.

Answer 1

You can find a maximum matching in a bipartite graph using network flow. The min cut max flow theorem translates to Hall's condition, so a min cut would give you the "evidence". See for example this document or this question on Mathematics.

Answer 2

I would use a degenerated version of the Hungarian algorithm (O(n^3)).

In the basic version on a U, V bipartite graph, you loop on the elements of x of U to give them the best assignement y from V. if y is already assigned, you make a growing subset X of U that may change their affectation without regret until:

• either X has at least |X| neighboors in V => then you move your assignements to add properly x.
• either X cannot grow anymore without regret and you accept to modify the weights (as the regret cannot be prevented).

For your problem, there is no weight. So if you are in the second case, just break off and you have your X subset. Else you will reach the last x of U and have a perfect assignement.