Overview
A 2-SAT implication graph adds edges !a -> b and !b -> a for every clause (a or b). The formula is unsatisfiable exactly when a variable and its negation belong to the same strongly connected component.
CoreSource checked
2-SAT Implication Graph
Solves 2-SAT by turning binary clauses into implications and checking strongly connected components.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- SAT Solving
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
- Aliases
- 2-SAT graph
Core Concepts
2-sat satisfiabilitysat solvingimplication graphoptimization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(2^n)
Worst
O(2^n)
Space
O(2^n)
When to Use
- Use when every clause has at most two literals.
- Use when a linear-time satisfiability check and assignment extraction are needed.
When Not to Use
- Avoid for general CNF formulas with clauses of length three or more.
- Avoid when optimization over satisfying assignments is required rather than feasibility.
What It Does
- 2-SAT Implication Graph uses turning binary clauses into implications and testing strongly connected components for 2-sat satisfiability
- Organizes the work around 2-sat satisfiability and sat solving.
Use Cases
- Production and research workloads requiring sat solving via The formula is unsatisfiable exactly when a variable and its negation belong to the same strongly connected component.
- SAT Solving pipelines where O(2^n) time and O(2^n) space fit system constraints.
- Engineering comparisons against Tarjan's Strongly Connected Components and Kosaraju's Algorithm when tuning sat solving.
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Key Formulas (1)
Clause implication
(a or b) becomes (!a → b) and (!b → a)
(a or b) becomes (!a -> b) and (!b -> a)Turns each binary clause into two directed implications.
Pseudocode
- 1.Create graph nodes for each literal and its negation
- 2.For each clause (a or b), add edges !a -> b and !b -> a
- 3.Compute strongly connected components
- 4.If any variable and its negation share an SCC, return unsatisfiable
- 5.Otherwise derive an assignment from SCC topological order
Canonical Example
- Input
- clauses (A or B) and (!A or B)
- Output
- satisfiable, with B = true as one valid choice
- Explanation
- The implication graph does not put any variable in the same SCC as its negation.
Implementation Notes
- Represent each variable with two nodes: x and !x.
- Run a strongly connected component algorithm on the implication graph.
- Assign variables by processing SCCs in reverse topological order.
Common Pitfalls
- Forgetting to add both implications for each clause changes the formula.
- Variable and negation indexing must be consistent across SCC construction.
- Satisfiability and assignment extraction are related but separate steps.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow turning binary clauses into implications and testing strongly connected components on a small 2-sat satisfiability example.
Step 1 of 5: Create graph nodes for each literal and its negation
optimization-mechanismNotes
The implication-graph test is specific to 2-CNF structure; it does not make general SAT easy.
Sources (1)
What each reference supports for this entry.
Handbook of Satisfiability
BookReference for 2-SAT Implication Graph within SAT solving, including search, simplification, learning, or local-search mechanisms.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesCDCL
Optimization · Core
Both address satisfiability, but they make different modeling or performance tradeoffs.
Compare with thisAlternative toDPLL
Optimization · Core
Both address 2-sat satisfiability, but they make different modeling or performance tradeoffs.
Compare with thisRelationships
View full relationship page2-SAT Implication Graph uses Tarjan's Strongly Connected Components as a subroutine, representation, or supporting idea while turning binary clauses into implications and testing strongly connected components.
2-SAT Implication Graph uses Kosaraju's Algorithm as a subroutine, representation, or supporting idea while turning binary clauses into implications and testing strongly connected components.
Alternative toDPLL
Both address 2-sat satisfiability, but they make different modeling or performance tradeoffs.
Related Algorithms
Tags
OptimizationConstraint Solving