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.