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:
If a perfect matching exists, it returns the matching;
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 $$
- $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.