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:
  • An -alternating path, for some matching, is a path in which the first edge is not an edge of, the second edge is of, the third is not of, etc.
  • A vertex is -reachable from some vertex, if there is an -alternating path from to.
As an example, consider the figure at the right, where the vertical edges denote the matching. The vertex sets, are -reachable from , but and are not -reachable from.
The algorithm for finding a Hall violator proceeds as follows.
  1. Find a maximum matching .
  2. If all vertices of are matched, then return "There is no Hall violator".
  3. Otherwise, let be an unmatched vertex.
  4. Let be the set of all vertices of that are -reachable from .
  5. Return .
This is indeed a Hall-violator because of the following facts:
  • All vertices of are matched by. Suppose by contradiction that some vertex in is unmatched by. Let be its neighbor in . The path from to to is an -augmenting path - it is -alternating and it starts and ends with unmatched vertices, so by "inverting" it we can increase, contradicting its maximality.
  • contains all the matches of by. This is because all these matches are -reachable from.
  • contains another vertex - - that is unmatched by by definition.
  • Hence,, so indeed satisfies the definition of a Hall violator.

    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 .
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.
  1. Set,,.
  2. Assert:
  3. * where the are distinct vertices of ;
  4. * where the are distinct vertices of ;
  5. * For all, is matched to by.
  6. * For all, is connected to some by an edge not in.
  7. If, then is a Hall violator, since. Return the Hall-violator .
  8. Otherwise, let be a vertex in Consider the following two cases:
  9. Case 1: is matched by.
  10. * Since is unmatched, and every in is matched to in, the partner of this must be some vertex of that is not in. Denote it by.
  11. * Let and and.
  12. * Go back to step 2.
  13. Case 2: is unmatched by.
  14. * Since is in, it is connected to some by an edge not in. is connected to by an edge in. is connected to some by an edge not in, and so on. Following these connections must eventually lead to, which is unmatched. Hence we have an M-augmenting path. Return the M-augmenting path.
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.