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.<ref>{{Cite arXiv|last=Lenchner|first=Jonathan|date=2020-01-19|title=On a Generalization of the Marriage Problem|class=math.CO|language=en|eprint=1907.05870v3}}</ref>

Formally, given a bipartite graph {{math|1=''G'' =&nbsp;(''X''&nbsp;+&nbsp;''Y'',&nbsp;''E'')}}, a Hall-violator in {{math|''X''}} is a subset {{math|''W''}} of {{math|''X''}}, for which {{math|{{!}}''N_G''(''W''){{!}} <&nbsp;{{!}}''W''{{!}}}}, where {{math|''N_G''(''W'')}} is the set of neighbors of {{math|''W''}} in&nbsp;{{math|''G''}}.

If {{math|''W''}} is a Hall violator, then there is no matching that saturates all vertices of {{math|''W''}}. Therefore, there is also no matching that saturates {{math|''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&nbsp;{{math|''X''}}.

== Algorithms == thumb|250x250px

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

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

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

The algorithm for finding a Hall violator proceeds as follows.

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

This {{math|''W''}} is indeed a Hall-violator because of the following facts:

* All vertices of {{math|''N_G''(''W'')}} are matched by {{math|''M''}}. Suppose by contradiction that some vertex {{math|''y''}} in {{math|''N_G''(''W'')}} is unmatched by {{math|''M''}}. Let {{math|''x''}} be its neighbor in ''{{math|W}}''. The path from {{math|''x''₀}} to {{math|''x''}} to {{math|''y''}} is an {{math|''M''}}-augmenting path - it is {{math|''M''}}-alternating and it starts and ends with unmatched vertices, so by "inverting" it we can increase {{math|''M''}}, contradicting its maximality. * {{math|''W''}} contains all the matches of {{math|''N_G''(''W'')}} by {{math|''M''}}. This is because all these matches are {{math|''M''}}-reachable from {{math|''x''₀}}. * {{math|''W''}} contains another vertex - {{math|''x''₀}} - that is unmatched by {{math|''M''}} by definition. * Hence, {{math|1={{!}}''W''{{!}} = {{!}}''N_G''(''W''){{!}} + 1 > {{!}}''N_G''(''W''){{!}}}}, so {{math|''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 {{math|''W''}}, then the remaining vertices can be perfectly matched to the vertices of {{math|''N_G''(''W'')}} (either by edges of {{math|''M''}}, or by edges of the M-alternating path from {{math|''x''₀}}).<ref>{{Cite journal|last1=Gan|first1=Jiarui|last2=Suksompong|first2=Warut|last3=Voudouris|first3=Alexandros A.|date=2019-09-01|title=Envy-freeness in house allocation problems|journal=Mathematical Social Sciences|volume=101|pages=104–106|doi=10.1016/j.mathsocsci.2019.07.005|issn=0165-4896|arxiv=1905.00468|s2cid=143421680}}</ref>

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 {{math|''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.<ref>Aditya Kabra. "[http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/1005 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 [https://cs.stackexchange.com/a/147733/1342 this CS stackexchange post].</ref>

=== Finding a Hall violator or an augmenting path === The following algorithm<ref>{{Cite web|url=https://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf|title=Bipartite Matching & the Hungarian Method|last=Mordecai J. Golin|date=2006|website=}}</ref><ref>{{Cite arXiv|last1=Segal-Halevi|first1=Erel|last2=Aigner-Horev|first2=Elad|date=2019-01-28|title=Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division|class=cs.DS|language=en|eprint=1901.09527v2}}</ref> takes as input an arbitrary matching {{math|''M''}} in a graph, and a vertex {{math|''x''₀}} in {{math|''X''}} that is not saturated by {{math|''M''}}.

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

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

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

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

== External links ==

* An application of Hall violators in constraint programming.<ref>{{Cite journal|last1=Elffers|first1=Jan|last2=Gocht|first2=Stephan|last3=McCreesh|first3=Ciaran|last4=Nordström|first4=Jakob|date=2020-04-03|title=Justifying All Differences Using Pseudo-Boolean Reasoning|url=https://ojs.aaai.org/index.php/AAAI/article/view/5507|journal=Proceedings of the AAAI Conference on Artificial Intelligence|language=en|volume=34|issue=2|pages=1486–1494|doi=10.1609/aaai.v34i02.5507|s2cid=208242680|issn=2374-3468|doi-access=free}}</ref> * {{Cite web|url=https://cs.stackexchange.com/q/30017/1342|title=Finding a subset in bipartite graph violating Hall's condition|date=2014-09-15|website=Computer science stack exchange|access-date=2019-09-08}}

== References == {{Reflist}}

Category:Graph theory objects Category:Matching (graph theory)