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$

Edges: $(a,x),(a,y),(b,z),(c,y)$

Exlusive pairs: $(b,z)$ and $(c,y)$

Answer: no perfect matching


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 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.