pith. sign in

arxiv: 1506.06157 · v1 · pith:PXSXA5YKnew · submitted 2015-06-19 · 💻 cs.DS · cs.DM· math.CO

Complexity of a Disjoint Matching Problem on Bipartite Graphs

classification 💻 cs.DS cs.DMmath.CO
keywords disjointproblemquestionsaturatessubsetwhenallowedappropriate
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.