3
$\begingroup$

Tarjan's algorithm for 2-SAT is based on the truth:

a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation.

But I don't find any reason for the right to left direction. how can the inexistence of such variable guarantee satisfaction of CNF?

I tried to follow the steps of the algorithm, and I was stuck here:

For each component in the reverse topological order, if its variables do not already have truth assignments, set all the literals in the component to be true. This also causes all of the literals in the complementary component to be set to false.

Isn't it possible the variable is already assigned WRONGLY? When we keep assigning TRUE from the back, and we assign the FALSE in the middle, but the TRUE is to be assigned to the next variable. In this case, the feasibility breaks.

Of course this kind of case never happens because the algorithm is right and many people use this algorithm well. But so many post says it as the trivial things.

  • I think the reason why those assignment is possible is relevant to the skew-symmetric condition of the graph, since (x -> ~x -> y -> ~y) never has true assignments.
$\endgroup$

2 Answers 2

2
$\begingroup$

a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation.

But I don't find any reason for the right to left direction. how can the inexistence of such variable guarantee satisfaction of CNF?

Think of a variable assignment for some unsatisfiable 2-SAT instance. This means one or more clauses must remain unsatisfied whatever the assignment. You change the setting of one or more variables to satisfy those clauses, but this unavoidably leaves some new clause or clauses unsatisfied because the instance is unsatisfiable. The failure of your change to satisfy the instance implies that some other variable's value must change. You repeat the procedure again and again, changing other variables as implication demands, but never succeed in satisfying all the clauses. Eventually, because the number of variables is finite, a failure implies that you change the value of a variable you've already visited... and that is your circular implication from $x$ to $\bar{x}$ back to $x$. Without a circular implication you will eventually reach the end of the implication chain and have a satisfying assignment. The only way not to reach the end of the chain is for the chain to be circular between a variable and its negation.

$\endgroup$
0
$\begingroup$

i need to see Tarjan original prrof because i also have a question regarding the algorithm,, so who can provide a link to some original paper or some will be higly appreciatef ... now, my question, it is known / provable that all variables in a strong component must have the same boolean value TRUE or FALSE. That is because you can reach from any variable of one strong component to any other variable in the same strong component, so if you have x and y in the same strong component you will have x->y and y->x and suposing either (x=FALSE and y=TRUE) or (x=TRUE and y=FALSE) will be a contradiction because TRUE->FALSE is a contradiction ... so the question you rise here still stands. suppose you set a variable x=TRUE in strong component S3 which implies setting variable ~x in strong component S2 to FALSE and in S2 there exists an variable y not assigned (that CAN happen because ~y is in strong component S1 an is not yet set) When you assign variables in S2 you will set y=TRUE which will lead to a contradiction because ~x=FALSE....

... and, now, i'll answer to " your right to left" question a variable x in a strong component Si can reach a variable y in a strong component Sj if i <j (but you cannot reach from any varible from Sj in one variable in Si i < j ) so you assign in first place y=TRUE beforec you set x. when you reach to set x either to TRUE or FALSE you will have either TRUE -> TRUE or FALSE -> TRUE which is no contradiction

$\endgroup$
5
  • 1
    $\begingroup$ Please don't use the 'Your Answer' box to ask a new question. Our site works differently from others you might be familiar with. We are not a discussion forum. We are a question-and-answer site with strict quality standards, and we require that answers must be focused only on answering the specific question at the top (not, e.g,. contributing related thoughts or questions). $\endgroup$
    – D.W.
    Jul 2, 2021 at 19:57
  • $\begingroup$ " . and, now, i'll answer to " your right to left" question " is not enough $\endgroup$ Jul 5, 2021 at 18:04
  • $\begingroup$ and "so the question you rise here still stands." clear sustain that this question did not get the right answer and like the one who posted i'm interesred (still) know the corect answer and does not denaturate the initial question, it only request more references that the previous answer while partially answer initial question. $\endgroup$ Jul 5, 2021 at 18:10
  • $\begingroup$ I find your answer very hard to read. The first two sentences appear to be a new request, which does not belong in an answer here. The third sentence, when you refer to "my question", makes it sound like you are raising a new question, which does not belong in an answer. I don't know what "still stands" means but if you are trying to say that there is something wrong with the other answer, which does not belong in an answer here. In the second paragraph I cannot understand the English. $\endgroup$
    – D.W.
    Jul 5, 2021 at 19:25
  • $\begingroup$ I encourage you to take the time to write with full sentences, with proper capitalization and punctuation and spelling, and use Latex/Mathjax. $\endgroup$
    – D.W.
    Jul 5, 2021 at 19:26

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.