Complexity of a Disjoint Matching Problem on Bipartite Graphs

Gregory J. Puleo

paper

Complexity of a Disjoint Matching Problem on Bipartite Graphs

arXiv:1506.06157

Abstract

We consider the following question: given an $(X, Y)$ -bigraph $G$ and a set $S \subset X$ , does $G$ contain two disjoint matchings $M_{1}$ and $M_{2}$ such that $M_{1}$ saturates $X$ and $M_{2}$ saturates $S$ ? When $∣ S ∣ \geq ∣ 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.

6 pages, 1 figure