Skip to content
Tutorials Center
My learning

Topics

Lesson 143 of 225 ยท Shortest Paths and Spanning Trees

2-SAT with Strongly Connected Components

Solve 2-SAT in linear time with Python: build the implication graph, find strongly connected components and read a satisfying assignment from component order.

Suppose a conference has to choose, for each of several talks, either the morning or the afternoon slot, and some pairs of talks cannot both happen in the same slot because they share a speaker. Or you must decide for each switch in a panel whether it is on or off, and each rule has the form "switch A is on or switch B is off". Both are instances of 2-SAT: a Boolean formula that is an AND of clauses, each clause an OR of two literals.

TEXT
(x1 or not x2) and (not x1 or x3) and (x2 or x3)

Satisfiability of general formulas (3-SAT) is NP-complete, but 2-SAT is solvable in linear time using the strongly connected components you met in Strongly Connected Components. This lesson builds the implication graph, solves the formula, and tests the solver against brute force. For complexity background see NP-completeness.

Clauses are implications

A clause (a or b) says: if a is false, then b must be true; and if b is false, then a must be true. In implication form:

TEXT
(a or b)   is equivalent to   (not a -> b)  and  (not b -> a)

Build a directed graph with 2n nodes: one for each variable x_i and one for its negation not x_i. For each clause add those two edges. A path p -> ... -> q means "if p is true then q must be true".

flowchart LR
  nx1["not x1"] --> nx2["not x2"]
  x2["x2"] --> x1["x1"]
  x1 --> x3["x3"]
  nx3["not x3"] --> nx1
  nx2 --> x3
  nx3 --> x2

The graph for (x1 or not x2), (not x1 or x3), (x2 or x3). Every clause produces two edges.

When is it unsatisfiable?

If a variable and its negation lie in the same strongly connected component, then x implies not x and not x implies x: a contradiction, so the formula is unsatisfiable. The reverse is also true: if no variable shares a component with its negation, a solution exists.

To construct the solution, use the topological order of the condensation graph. Set x = true if the component of x comes later in topological order than the component of not x (that is, x is closer to the "sinks"). Reasoning: truth should flow forward along implications, so we set to true the literal that does not force anything false later.

With Tarjan's algorithm, components are numbered in reverse topological order (the first component found is a sink). So use x = true when comp[x] < comp[not x].

Implementation

We represent variable i (0-based) as node 2*i and its negation as 2*i + 1; the opposite of node v is v ^ 1. A literal is given as a signed integer: +k for x_k and -k for not x_k (1-based, like the DIMACS format).

Python 2-SAT solver with iterative Tarjan

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solver is O(n + m) for n variables and m clauses: the graph has 2n nodes and 2m edges, and Tarjan visits each once. The iterative version avoids Python's recursion limit on big inputs.

A practical model: choosing slots

Each talk is either in the morning (x_i true) or the afternoon (x_i false). If talks i and j share a speaker, they cannot be at the same time. That is two clauses: "not both morning" is (not x_i or not x_j) and "not both afternoon" is (x_i or x_j). Add forced slots as single-literal clauses (a or a).

Python Scheduling with 2-SAT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that with Kosaraju the component numbering follows the topological order, so the comparison flips: x = true when comp[x] > comp[not x]. The rule is always "pick the literal whose component is later in topological order".

A triangle of conflicts is unsatisfiable: three talks that all pairwise conflict would need three different slots, but only two exist. This is the same as asking whether a graph is bipartite, and 2-SAT generalizes that question.

Where 2-SAT appears

  • Deciding teams or sides when pairs must differ or must agree.
  • Layout and placement problems: each object has two possible positions, and some pairs of choices collide.
  • Exactly-one or at-most-one constraints over two items.
  • Checking consistency of small constraint sets in configuration tools.

For clauses with three or more literals, the same graph trick does not work; the problem becomes NP-complete.

Common mistakes

  • Adding only one of the two implications for a clause. Always add both not a -> b and not b -> a.
  • Mixing up the component order rule between Tarjan (reverse topological) and Kosaraju (topological).
  • Forgetting single-literal clauses: encode "a must be true" as (a or a), which gives the edge not a -> a.
  • Recursive DFS on large inputs, which can overflow Python's stack. Use an iterative version.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A 2-SAT formula is unsatisfiable exactly when:

    If x and not x reach each other, x implies not x and not x implies x, so neither value works. Plain cycles elsewhere in the graph are fine.
  2. 2. Which edges does the clause (a or b) add to the implication graph?

    If a is false then b must be true, and if b is false then a must be true. Both implications are needed.
  3. 3. With Tarjan's numbering (first completed component gets number 0), x is set to true when:

    Tarjan numbers components in reverse topological order, so a smaller number means later in topological order, which is the literal we should make true.
  4. 4. What is the running time of the 2-SAT algorithm with n variables and m clauses?

    The graph has 2n nodes and 2m edges, and one SCC pass visits each once.

Summary

  • Every 2-SAT clause (a or b) becomes two implications not a -> b and not b -> a in a graph with 2n literal nodes.
  • Unsatisfiable exactly when a variable and its negation share a strongly connected component.
  • Otherwise set each variable true when its literal's component is later in topological order.
  • The whole solution runs in O(n + m); verify it against brute force on small formulas.
  • Three-literal clauses (3-SAT) are NP-complete and need different techniques.

Next: Bridges and Articulation Points