2-Sat to Implication Graph

409 Views Asked by At

I have a set of clauses

$$(x,y),(x,z),(y,z),(\neg x, \neg y), (\neg x , \neg z), ( \neg y, \neg z)$$

I drew the implication graph and have no bad loop but the answer says there is a bad loop.

My graph I'm pretty sure is wrong.

I drew

x->y->y with a line from x->y

and the same for the negation but this doesn't contain a bad loop so my graph must be wrong.

1

There are 1 best solutions below

1
On BEST ANSWER

If $p \lor q$ is a clause in your 2-Sat instance, then in the implication graph this gives two arrows, namely $\neg p \to q$ and $\neg q \to p$. (Namely, the clause says that if $p$ is false then $q$ must be true, and if $q$ is false then $p$ must be true in order to make the clause true.)

For instance, from $(x,y)$ you get arrows $\neg x \to y$ and $\neg y \to x$. From $(\neg y,\neg z)$ you get arrows $y \to \neg z$ and $z \to \neg y$.

Can you find the correct graph now? And the bad loop in your graph? Hint for checking your answer: it goes past all 6 vertices of the graph.