4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Yuval Filmus
    Commented Sep 1, 2020 at 11:40
  • $\begingroup$ 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$? $\endgroup$
    – Erel Segal-Halevi
    Commented Sep 1, 2020 at 12:17
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Yuval Filmus
    Commented Sep 1, 2020 at 12:19
  • 1
    $\begingroup$ 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). $\endgroup$
    – user114966
    Commented Sep 1, 2020 at 12:41

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.