Is Tarjan's algorithm capable of finding satisfying assignment to any digraph consists of variables (vertices) and implications (edges)? I know that it solves implication graphs constructed by 2SAT clauses, but I wonder if the algorithm can handle the digraphs which cannot be expressed as 2SAT clauses. Let me clarify this by the following examples:
(a+b)(~b+c) translates to the following (~a -> b), (~b -> a), (b -> c), (~c -> ~b) It is OK. But how about the following implications: (a -> b), (b -> ~c) There is obviously no corresponding set of 2SAT instances. Does Tarjan's algorithm find a satisfying assignment to this?