{{short description|Graph matching with max number of high-priority vertices}}
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 {{math|1=''G'' = (''V'', ''E'')}}, and a partition of the vertex-set {{mvar|V}} into some {{mvar|k}} subsets, {{math|''V''{{sub|1}}, …, ''V{{sub|k}}''}}, called ''priority classes''. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from {{math|''V''{{sub|1}}}}; subject to this, it saturates the largest number of vertices from {{math|''V''{{sub|2}}}}; subject to this, it saturates the largest number of vertices from {{math|''V''{{sub|3}}}}; and so on.
Priority matchings were introduced by Alvin Roth, Tayfun Sonmez and Utku Unver<ref>{{Cite journal|last1=Roth|first1=Alvin E.|last2=Sönmez|first2=Tayfun|last3=Utku Ünver|first3=M.|date=2005-12-01|title=Pairwise kidney exchange|journal=Journal of Economic Theory|language=en|volume=125|issue=2|pages=151–188|doi=10.1016/j.jet.2005.04.004|s2cid=583399|issn=0022-0531|url=http://papers.nber.org/papers/w10698.pdf }}</ref> in the context of kidney exchange. In this problem, the vertices are patient-donor pairs, and each edge represents a mutual medical compatibility. For example, an edge between pair 1 and pair 2 indicates that donor 1 is compatible with patient 2 and donor 2 is compatible with patient 1. The priority classes correspond to medical priority among patients. For example, some patients are in a more severe condition so they must be matched first. Roth, Sonmez and Unver assumed that each priority-class contains a single vertex, i.e., the priority classes induce a total order among the pairs.
Later, Yasunori Okumura<ref>{{Cite journal|last=Okumura|first=Yasunori|date=2014-11-01|title=Priority matchings revisited|journal=Games and Economic Behavior|language=en|volume=88|pages=242–249|doi=10.1016/j.geb.2014.10.007|issn=0899-8256}}</ref> extended the work to priority-classes that may contain any number of vertices. He also showed how to find a priority matching efficiently using an algorithm for maximum-cardinality matching, with a run-time complexity of {{math|''O''({{abs|''V''}}{{abs|''E''}} + {{abs|''V''}}{{sup|2}} log {{abs|''V''}})}}.
Jonathan S. Turner<ref>{{cite arXiv|last=Turner|first=Jonathan|date=2015-12-28|title=Maximium [sic] Priority Matchings|class=cs.DS|eprint=1512.08555}}</ref> presented a variation of the augmenting path method (Edmonds' algorithm) that finds a priority matching in time {{math|''O''({{abs|''V''}}{{abs|''E''}})}}. Later, he found a faster algorithm for bipartite graphs: the algorithm runs in time<ref>{{cite arXiv|last=Turner|first=Jonathan|date=2015-12-31|title=Faster Maximium [sic] Priority Matchings in Bipartite Graphs|class=cs.DS|eprint=1512.09349}}</ref> :<math>O(k |E| \sqrt{|V|} )</math>
== See also ==
* Maximum cardinality matching * Rank-maximal matching
== References == {{Reflist}}
Category:Matching (graph theory)