Priority matching

Summary

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}, \ldots, 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.