Pergunta

I learned finding a solution of 2-sat problem algorithm below.

The point are below

(1) when constructing the implication graph

(2) finding there is no occurrence of a variable x and its negation x' in any SCC in the graph.

(3) then there is always the solution at this 2-SAT problem.

it means that all false 2-SAT problem have a variable x and its negation x' in SCC of its implication graph.

I cannot understand this point (3).

How can I prove it has a solution if only if there is no x and x' in a SCC?

It looks like to me, although there is no x and x' in SCC, it can be false.

enter image description here

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top