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