# Perfect Matching in Bipartite Graph with mutually exclusive edges

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.

## 1 Answer

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}$$.