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.^[1]

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 1, X 1, Y 2, X 2$ , are $M$ -reachable from $x 0$ (or any other vertex of $X 0$ ), but $Y 3$ and $X 3$ are not $M$ -reachable from $x 0$ .

The algorithm for finding a Hall violator proceeds as follows.

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

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 0$ 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.^[3]

Finding a Hall violator or an augmenting path

The following algorithm^[4]^[5] takes as input an arbitrary matching $M$ in a graph, and a vertex $x 0$ in $X$ that is not saturated by $M$ .

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

Set $k = 0$ , $W k := {x 0$ }, $Z k := {}$ .
Assert:
- $W k = {x 0,..., x k}$ where the $x i$ are distinct vertices of $X$ ;
- $Z k = {y 1,..., y k}$ where the $y i$ are distinct vertices of $Y$ ;
- For all $i \geq 1$ , $y i$ is matched to $x i$ by $M$ .
- For all $i \geq 1$ , $y i$ is connected to some $x j < i$ by an edge not in $M$ .
If $N G (W k) \subseteq Z k$ , then $W k$ is a Hall violator, since $| W k | = k +1 > k = | Z k | \geq | N G (W k)|$ . Return the Hall-violator $W k$ .
Otherwise, let $y k +1$ be a vertex in $NG(Wk) \ Zk.$ Consider the following two cases:
Case 1: y_k+1 is matched by M.
- Since $x 0$ 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.
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 0$ , 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.^[6]
"Finding a subset in bipartite graph violating Hall's condition". Computer science stack exchange. 2014-09-15. Retrieved 2019-09-08.{{cite web}}: CS1 maint: url-status (link)

References

^ Lenchner, Jonathan (2020-01-19). "On a Generalization of the Marriage Problem". arXiv:1907.05870v3 [math.CO].
^ Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (2019-09-01). "Envy-freeness in house allocation problems". Mathematical Social Sciences. 101: 104–106. arXiv:1905.00468. doi:10.1016/j.mathsocsci.2019.07.005. ISSN 0165-4896. S2CID 143421680.
^ Aditya Kabra. "Parameterized Complexity of Minimum k Union Problem". MS Thesis. Theorem 3.2.5. This is also Exercise 13.28 in [4] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dniel Marx, Marcin Pilipczuk, Micha Pilipczuk and Saket Saurabh, "Parameterized Algorithms", Springer, 2016. See also this CS stackexchange post.
^ Mordecai J. Golin (2006). "Bipartite Matching & the Hungarian Method" (PDF).
^ Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). "Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division". arXiv:1901.09527v2 [cs.DS].
^ Elffers, Jan; Gocht, Stephan; McCreesh, Ciaran; Nordström, Jakob (2020-04-03). "Justifying All Differences Using Pseudo-Boolean Reasoning". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1486–1494. doi:10.1609/aaai.v34i02.5507. ISSN 2374-3468. S2CID 208242680.

[1] Lenchner, Jonathan (2020-01-19). "On a Generalization of the Marriage Problem". arXiv:1907.05870v3 [math.CO].

[2] Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (2019-09-01). "Envy-freeness in house allocation problems". Mathematical Social Sciences. 101: 104–106. arXiv:1905.00468. doi:10.1016/j.mathsocsci.2019.07.005. ISSN 0165-4896. S2CID 143421680.

[3] Aditya Kabra. "Parameterized Complexity of Minimum k Union Problem". MS Thesis. Theorem 3.2.5. This is also Exercise 13.28 in [4] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dniel Marx, Marcin Pilipczuk, Micha Pilipczuk and Saket Saurabh, "Parameterized Algorithms", Springer, 2016. See also this CS stackexchange post.

[4] Mordecai J. Golin (2006). "Bipartite Matching & the Hungarian Method" (PDF).

[5] Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). "Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division". arXiv:1901.09527v2 [cs.DS].

[6] Elffers, Jan; Gocht, Stephan; McCreesh, Ciaran; Nordström, Jakob (2020-04-03). "Justifying All Differences Using Pseudo-Boolean Reasoning". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1486–1494. doi:10.1609/aaai.v34i02.5507. ISSN 2374-3468. S2CID 208242680.

[1]

[2]

[3]

[4]

[5]

[6]