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

#1 chloeCodes   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • 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?

Thanks in advance
Is This A Good Question/Topic? 0
  • +

Replies To: Understanding implication graph /2sat algorithm

#2 sepp2k   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2740
  • View blog
  • 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:

View Postsepp2k, 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

Was This Post Helpful? 1
  • +
  • -

#3 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12617
  • View blog
  • 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/
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1