Graph Theory37 sections · 1633 units
Open in Course

When to Use 2-SAT

(Problem recognition)

Use 22-SAT when: (11) You have binary choices for each variable. (22) Constraints are "at least one of two conditions must hold." (33) You need to find any valid assignment, not count them or find the best one. If you see these patterns, model it as 22-SAT and use the SCC algorithm.

If constraints involve three or more variables per clause, you need a different approach. 22-SAT is effective but limited to this specific structure. Do not force problems into 22-SAT if they do not fit.