# Understanding implication graph /2sat algorithm

Page 1 of 1

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

### #1 chloeCodes

Reputation: 4
• Posts: 227
• Joined: 05-January 17

# Understanding implication graph /2sat algorithm

Posted 07 November 2018 - 05:05 PM

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?

Is This A Good Question/Topic? 0

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

### #2 sepp2k

• D.I.C Lover

Reputation: 2740
• Posts: 4,392
• Joined: 21-June 11

## 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 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?

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

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12617
• Posts: 45,776
• Joined: 27-December 08

## 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/