Perfect Matching in Bipartite Graph with mutually exclusive edges
-
29-09-2020 - |
Question
Problem
I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive.
Example
Left vertices: $a,b,c$
Right vertices: $x,y,z$
Edges: $(a,x),(a,y),(b,z),(c,y)$
Exlusive pairs: $(b,z)$ and $(c,y)$
Answer: no perfect matching
Question
Is the problem in P or NP?
Solution Attempts
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.
Solution
It is $NP$ as $SAT$ can be polynomially reduced to this problem.
Let clauses be the left part vertexes, and literals be the right part vertexes. Draw an edge $(x,y)$ iff clause $x$ contains literal $y$. Finally, a pair of edges $(x_1, y_1)$ and $(x_2, y_2)$ will be exclusive iff $y_1$ corresponds to literal $a$ and $y_2$ corresponds to literal $\overline{a}$.