Why it matters

2-SAT solvable polynomially unlike general SAT. Understanding enables many problems.

Advertisement

The architecture

Implication graph: for each clause (a ∨ b), add edges ¬a → b and ¬b → a.

SCC on graph.

2-SAT solutionImplication graphfrom clausesSCC via Tarjanfind componentsCheckno variable + neg in same SCCAssignment: reverse topological order via SCC; assign true to later component
2-SAT via SCC.
Advertisement

How it works end to end

Satisfiable iff no variable and its negation in same SCC.

Assignment: reverse topological order of SCCs; set var true if its SCC after ¬var's SCC.

Applications: scheduling with pairwise constraints, some game problems.