Hall violator

[1] Formally, given a bipartite graph G = (X + Y, E), a Hall-violator in X is a subset W of X, for which |NG(W)| < |W|, where NG(W) is the set of neighbors of W in G. If W is a Hall violator, then there is no matching that saturates all vertices of W. Therefore, there is also no matching that saturates X.

The above algorithm, in fact, finds an inclusion-minimal Hall violator.

[2] The above algorithm does not necessarily find a minimum-cardinality Hall violator.

In fact, finding a minimum-cardinality Hall violator is NP-hard.

[3] The following algorithm[4][5] takes as input an arbitrary matching M in a graph, and a vertex x0 in X that is not saturated by M. It returns as output, either a Hall violator that contains x0, or a path that can be used to augment M. At each iteration, Wk and Zk grow by one vertex.