3

An implication graph is a directed graph where each node is assigned either true or false and any edge u -> v implies that if u is true then v is true.

I know a straightforward O(n^2) algorithm to find an assignment in a general implication graph and O(n) algorithms for some special cases (like the implication graph arising from a 2-SAT problem).

So I was wondering if there is an O(n) algorithm find assignment of any implication graph?

subspring
  • 690
  • 2
  • 7
  • 23
Corei13
  • 401
  • 2
  • 9
  • You didn't specify what are the requirements for the assignment. – piotrekg2 Sep 20 '14 at 19:50
  • Can you give a simple example of an implication graph that is not equivalent to a 2-SAT problem? (I thought all implication graphs are equivalent to 2-SAT and can all be solved in O(n) by Tarjan's strongly connected components algorithm) – Peter de Rivaz Sep 20 '14 at 20:02
  • @piotrekg2, each edge specify a requirement. An edge from node u to node v means if u is assigned true then v must be true also. – Corei13 Sep 20 '14 at 20:40
  • 1
    How is that not equivalent to the 2SAT formula (!a OR !b) AND (!b OR c)? The general idea is to replace x -> y with !x OR y. – David Eisenstat Sep 20 '14 at 20:47

1 Answers1

1

Satisfying assignments for implication graphs can be found using the Tarjan strongly connected components method since that method is applicable to all implication graphs, not just those produced via conversion of 2-SAT instances. That method consists of a small number of graph conversion steps, all of which require time linear to the size of the input. Thus the algorithm as a whole requires O(n) runtime.

Kyle Jones
  • 5,492
  • 1
  • 21
  • 30