Hall violator

Last updated September 28, 2023

In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem.^[1]

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.

Related Research Articles

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph $G = (V, E)$ , a perfect matching in $G$ is a subset $M$ of edge set $E$ , such that every vertex in the vertex set $V$ is adjacent to exactly one edge in $M$ .

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite undirected graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs. It is a special case of the Tutte–Berge formula.

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph. At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most $Δ+µ$ colors, where $µ$ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph $G$ , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In graph theory, a mathematical discipline, a factor-critical graph is a graph with $n$ vertices in which every subgraph of $n - 1$ vertices has a perfect matching.

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs.

In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph $G = (V, E)$ , the algorithm finds a matching $M$ such that each vertex in $V$ is incident with at most one edge in $M$ and $| M |$ is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.

In economics and social choice theory, an envy-free matching (EFM) is a matching between people to "things", which is envy-free in the sense that no person would like to switch his "thing" with that of another person. This term has been used in several different contexts.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.

Deficiency is a concept in graph theory that is used to refine various theorems related to perfect matching in graphs, such as Hall's marriage theorem. This was first studied by Øystein Ore. A related property is surplus.

In graph theory, a priority matching (also called: maximum priority matching) is a matching that maximizes the number of high-priority vertices that participate in the matching. Formally, we are given a graph $G = (V, E)$ , and a partition of the vertex-set $V$ into some $k$ subsets, $V 1, \dots, V k$ , called priority classes. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from $V 1$ ; subject to this, it saturates the largest number of vertices from $V 2$ ; subject to this, it saturates the largest number of vertices from $V 3$ ; and so on.

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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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