0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

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

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