Hall violator
In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem. Formally, given a bipartite graph , a Hall-violator in is a subset of , for which , where is the set of neighbors of in . If is a Hall violator, then there is no matching that saturates all vertices of . Therefore, there is also no matching that saturates . Hall's marriage theorem says that the opposite is also true: if there is no Hall violator, then there exists a matching that saturates . Algorithms. Finding a Hall violator . A Hall violator can be found by an efficient algorithm. The algorithm below uses the following terms: As an example, consider the figure at the right, where the vertical (blue) edges denote the matching . The vertex sets , are -reachable from (or any other vertex of ), but and are not -reachable from . The algorithm for finding a Hall violator proceeds as follows. This is indeed a Hall-violator because of the following facts: Finding minimal and minimum Hall violators. An inclusion-minimal Hall violator is a Hall violator such that each of its subsets is not a Hall violator. The above  algorithm, in fact, finds an inclusion-minimal Hall violator. This is because, if any vertex is removed from , then the remaining vertices can be perfectly matched to the vertices of (either by edges of , or by edges of the M-alternating path from ). The above algorithm does not necessarily find a minimum-cardinality Hall violator. For example, in the above figure, it returns a Hall violator of size 5, while is a Hall violator of size 3. In fact, finding a minimum-cardinality Hall violator is NP-hard. This can be proved by reduction from the Clique problem. Finding a  Hall violator or an augmenting path. The following algorithm takes as input an arbitrary matching in a graph, and a vertex in that is not saturated by . It returns as output, either a Hall violator that contains , or a path that can be used to augment . At each iteration, and grow by one vertex. Hence, the algorithm must finish after at most iterations. The procedure can be used iteratively: start with being an empty matching, call the procedure again and again, until either a Hall violator is found, or the matching saturates all vertices of . This provides a constructive proof  to Hall's theorem.