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 G = (X + Y, E), a Hall-violator in X is a subset W of X, for which |N_G(W)| < |W|, where N_G(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. Hall's marriage theorem says that the opposite is also true: if there is no Hall violator, then there exists a matching that saturates X.

Algorithms

Finding a Hall violator

A Hall violator can be found by an efficient algorithm. The algorithm below uses the following terms:

• An M-alternating path, for some matching M, is a path in which the first edge is not an edge of M, the second edge is of M, the third is not of M, etc.
• A vertex z is M-reachable from some vertex x, if there is an M-alternating path from x to z.

As an example, consider the figure at the right, where the vertical (blue) edges denote the matching M. The vertex sets Y₁, X₁,Y₂, X₂, are M-reachable from x₀ (or any other vertex of X₀), but Y₃ and X₃ are not M-reachable from x₀.

The algorithm for finding a Hall violator proceeds as follows.

1. Find a maximum matching M (it can be found with the Hopcroft–Karp algorithm).
2. If all vertices of X are matched, then return "There is no Hall violator".
3. Otherwise, let x₀ be an unmatched vertex.
4. Let W be the set of all vertices of X that are M-reachable from x₀ (it can be found using Breadth-first search; in the figure, W contains x₀ and X₁ and X₂).
5. Return W.

This W is indeed a Hall-violator because of the following facts:

• All vertices of N_G(W) are matched by M. Suppose by contradiction that some vertex y in N_G(W) is unmatched by M. Let x be its neighbor in W. The path from x₀ to x to y is an M-augmenting path - it is M-alternating and it starts and ends with unmatched vertices, so by "inverting" it we can increase M, contradicting its maximality.
• W contains all the matches of N_G(W) by M. This is because all these matches are M-reachable from x₀.
• W contains another vertex - x₀ - that is unmatched by M by definition.
• Hence, |W| = |N_G(W)| + 1 > |N_G(W)|, so W 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 W, then the remaining vertices can be perfectly matched to the vertices of N_G(W) (either by edges of M, or by edges of the M-alternating path from x₀).

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 X₀ 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 M in a graph, and a vertex x₀ in X that is not saturated by M.

It returns as output, either a Hall violator that contains x₀, or a path that can be used to augment M.

1. Set k = 0, W_k := {x₀}, Z_k := {}.
2. Assert:
   • W_k = {x₀,...,x_k} where the x_i are distinct vertices of X;
   • Z_k = {y₁,...,y_k} where the y_i are distinct vertices of Y;
   • For all i ≥ 1, y_i is matched to x_i by M.
   • For all i ≥ 1, y_i is connected to some x_j<i by an edge not in M.
3. If N_G(W_k) ⊆ Z_k, then W_k is a Hall violator, since |W_k| = k+1 > k = |Z_k| ≥ |N_G(W_k)|. Return the Hall-violator W_k.
4. Otherwise, let y_k+1 be a vertex in N_G(W_k) \ Z_k. Consider the following two cases:
5. Case 1: y_k+1 is matched by M.
   • Since x₀ is unmatched, and every x_i in W_k is matched to y_i in Z_k, the partner of this y_k+1 must be some vertex of X that is not in W_k. Denote it by x_k+1.
   • Let W_k+1 := W_k U {x_k+1} and Z_k+1 := Z_k U {y_k+1} and k := k + 1.
   • Go back to step 2.
6. Case 2: y_k+1 is unmatched by M.
   • Since y_k+1 is in N_G(W_k), it is connected to some x_i (for i < k + 1) by an edge not in M. x_i is connected to y_i by an edge in M. y_i is connected to some x_j (for j < i) by an edge not in M, and so on. Following these connections must eventually lead to x₀, which is unmatched. Hence we have an M-augmenting path. Return the M-augmenting path.

At each iteration, W_k and Z_k grow by one vertex. Hence, the algorithm must finish after at most |X| iterations.

The procedure can be used iteratively: start with M being an empty matching, call the procedure again and again, until either a Hall violator is found, or the matching M saturates all vertices of X. This provides a constructive proof to Hall's theorem.

External links

• An application of Hall violators in constraint programming.
• "Finding a subset in bipartite graph violating Hall's condition". 2014-09-15. https://cs.stackexchange.com/q/30017/1342.