Complexity of a disjoint matching problem on bipartite graphs

• We consider the problem of finding two disjoint matchings in a bipartite graph.
• One matching should be perfect, the other should saturate some given vertex set.
• We prove that this problem is NP-hard.
• This strengthens a hardness result due to Frieze.

We consider the following question: given an (X,Y)(X,Y)-bigraph G   and a set S⊆XS⊆X, does G   contain two disjoint matchings M1M1 and M2M2 such that M1M1 saturates X   and M2M2 saturates S  ? When |S|≥|X|−1|S|≥|X|−1, this question is solvable by finding an appropriate factor of the graph. In contrast, we show that when S is allowed to be an arbitrary subset of X, the problem is NP-hard.