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 (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.

# Find a maximum matching (it can be found with the Hopcroft–Karp algorithm).
# If all vertices of are matched, then return "There is no Hall violator".
# Otherwise, let be an unmatched vertex.
# Let be the set of all vertices of that are -reachable from (it can be found using Breadth-first search; in the figure, contains and and ).
# 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 (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 .

# Set , , .
# Assert:
#* where the are distinct vertices of ;
#* where the are distinct vertices of ;
#* For all , is matched to by .
#* For all , is connected to some by an edge not in .
# If , then is a Hall violator, since . Return the Hall-violator .
# Otherwise, let be a vertex in Consider the following two cases:
# Case 1: is matched by .
#* 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 .
#* Let and and .
#* Go back to step 2.
# Case 2: is unmatched by .
#* Since is in , it is connected to some (for ) by an edge not in . is connected to by an edge in . is connected to some (for ) 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.

External links

* An application of Hall violators in constraint programming.
*

References

{{Reflist

Graph theory