I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive.
Left vertices: $a,b,c$
Right vertices: $x,y,z$
Exlusive pairs: $(b,z)$ and $(c,y)$
Answer: no perfect matching
Is the problem in P or NP?
I know that Perfect Matching in Bipartite Graph Problem is in P. But I cannot find a polynomial-time algorithms for the above version of this problem. I have also tried proving that it is NP, but without any luck.