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.

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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