Find a maximum matching that saturates a given set of vertices

Question

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?

Answer 1

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.