Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427031 | Information Processing Letters | 2016 | 4 Pages |
Abstract
•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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gregory J. Puleo,