# Find a maximum matching that saturates a given set of vertices

In an unweighted bipartite graph $$G = (X + Y,E)$$, we would like to find a maximum matching, but among all those maximum matchings, we would like to find one that saturates a given subset $$X_0\subseteq X$$.

A necessary condition for the existence of such a matching is that $$X_0$$ satisfies Hall's marriage condition, i.e., for every $$X'\subseteq X_0$$, the number of neighbors of $$X'$$ is at least $$|X'|$$. If this condition is satisfied, we can find a matching $$M$$ that saturates all vertices of $$X_0$$, but $$M$$ is not necessarily a maximum matching in $$G$$.

Is it always possible to extend $$M$$ into a maximum matching? Alternatively, is there a different way to find a maximum matching that saturates $$X_0$$ when the necessary condition is satisfied?

• What happens if you additively boost the weight of each edge touching $X_0$ so that a maximum matching must contain the maximum number of such edges? Sep 1, 2020 at 11:40
• Do you mean to assign a weight of $W \gg 1$ to each edge adjacent to $X_0$, and a weight of $1$ to all other edges, and find a maximum-weight matching? This will indeed maximize the number of matched vertices of $X_0$, and subject to this, the number of matched vertices of $X$. But will it necessarily be a maximum cardinality matching in $G$? Sep 1, 2020 at 12:17
• In that case, you can try an opposite approach: given edges not adjacent to $X_0$ a weight of $1$, and those adjacent to $X_0$ a weight of $1+\epsilon$. Sep 1, 2020 at 12:19
• Do I understand correctly that your question is "Find matching such that 1) it has the maximum number of edges 2) each vertex from $X_0$ has an adjacent edge in this matching"? Then you can just use Kuhn's algorithm, where you first process vertices from $X_0$ (if for some such vertex an augmented path wasn't found, such matching doesn't exist). This works since a saturated vertex will remain saturated. And yes, it'll find the maximum matching (since, well, Kuhn's algorithm is correct).
– user114966
Sep 1, 2020 at 12:41

After some research, I found out that my question is a special case of the problem of priority matching. In this case there are two priority classes, $$X_0$$ and $$X_1 := V\setminus X_0$$. The goal is to find a matching that maximizes the number of saturated vertices in $$X_0$$, and subject to that, the number of saturated vertices in $$X_1$$. There are efficient algorithms that solve this problem for any number of priority classes. It is known that any priority matching is also a maximum-cardinality matching.