Could someone kindly explain whether the implication graph show here: https://cs.stackexch...r-2-sat-clauses

Does the implication graph contain a Strongly Connected Component (SCC) if so could you explicitly say between which nodes it exists?

Thanks in advance

# Understanding implication graph /2sat algorithm

Page 1 of 1## 2 Replies - 415 Views - Last Post: 07 November 2018 - 08:25 PM

##
**Replies To:** Understanding implication graph /2sat algorithm

### #2

## Re: Understanding implication graph /2sat algorithm

Posted 07 November 2018 - 06:05 PM

Are you talking about the one in the question or the answer?

Do you understand what a strongly connected component is? Do

The OP of the linked question mentions infinite loops. What does that mean in the context of strongly connected components?

Edit:

I've just noticed that the answer to the linked question already answers that.

Do you understand what a strongly connected component is? Do

*you*think the graph contains one?The OP of the linked question mentions infinite loops. What does that mean in the context of strongly connected components?

Edit:

sepp2k, on 08 November 2018 - 02:03 AM, said:

The OP of the linked question mentions infinite loops. What does that mean in the context of strongly connected components?

I've just noticed that the answer to the linked question already answers that.

This post has been edited by **sepp2k**: 07 November 2018 - 06:05 PM

### #3

## Re: Understanding implication graph /2sat algorithm

Posted 07 November 2018 - 08:25 PM

Tarjan's algorithm can detect strongly connected components. Try using that (as well as the answer provided in the stackexchange thread).

Also, for interested folks, my tutorial on P and NP has a proof that 2-SAT is in P.

https://www.dreaminc...asses-p-and-np/

Also, for interested folks, my tutorial on P and NP has a proof that 2-SAT is in P.

https://www.dreaminc...asses-p-and-np/

Page 1 of 1