2-SAT and Max 2-SAT

Overview

Kent Quanrud contrasts 2-SAT, which can be solved in linear time using an implication graph and strongly connected components, with Max 2-SAT, whose optimization version is NP-hard. He also constructs a reduction from 3-SAT using a 10-clause gadget that scores at most 6 when a 3-literal clause is false and 7 when it is true, then pads singleton clauses to obtain exactly two literals per clause.

Key takeaways

For a 2-SAT clause (A ∨ B), the implication edges ¬A → B and ¬B → A encode all forced consequences of the clause.
A 2-SAT formula is satisfiable exactly when no variable xᵢ and its negation ¬xᵢ belong to the same strongly connected component.
The SCC condensation graph is a DAG, and complement-paired source and sink components enable a consistent truth assignment in linear time.
Max 2-SAT is NP-hard even with exactly two literals per clause: a 3-SAT formula with m clauses maps to an instance whose optimum reaches 7m exactly when the original formula is satisfiable.
The 10-clause gadget creates a one-point gap: it can score at most 6 when all three literals are false and can score 7 whenever at least one is true.
Replacing a singleton clause A by (A ∨ y) and (A ∨ ¬y) adds a fixed one-point offset, allowing at-most-2-literal instances to become exact-2-literal instances without changing the optimization decision.

Chapters

0:00 SAT, CNF, and Why Simpler Formulas Can Still Be Hard

SAT asks whether any Boolean assignment makes a formula true; checking one assignment is easy, but trying all assignments can take exponential time.
Earlier reductions showed that CNF-SAT and 3-SAT can encode more general Boolean satisfiability problems.
The lecture narrows the focus to clauses with two literals and compares full satisfiability with maximizing the number of satisfied clauses.

4:30 2-SAT Versus Max 2-SAT: The Optimization Question

2-SAT asks whether every clause, each containing two literals, can be satisfied simultaneously.
Max 2-SAT instead gives each clause one point and seeks an assignment satisfying as many clauses as possible.
A decision oracle for Max 2-SAT can answer whether at least K clauses are satisfiable; setting K to the total clause count solves 2-SAT.

11:30 Why 2-SAT Constraints Create Forced Assignments

In a clause such as (x₁ ∨ x₂), setting x₁ false forces x₂ true.
These implications can trigger chains of forced values, unlike 3-SAT choices that may leave multiple literals available.
That forced structure motivates a graph representation rather than a brute-force search over assignments.

16:00 Building the 2-SAT Implication Graph

Create two vertices for each variable: one for xᵢ and one for ¬xᵢ, representing the two possible literal values.
For each clause (A ∨ B), add edges ¬A → B and ¬B → A, encoding the consequences of either literal being false.
Each two-literal clause therefore contributes two directed edges to a graph with 2n literal vertices.

20:00 Reading Satisfying Assignments from Graph Edges

A literal assignment satisfies the formula exactly when no implication edge goes from a true vertex to a false vertex.
False-to-true edges and edges whose endpoints share a value do not violate the implication.
For the illustrated four-clause formula, the assignment x₁=false, x₂=true avoids every true-to-false edge.

24:00 Contradictions as Cycles Between Complementary Literals

If xᵢ and ¬xᵢ lie in the same strongly connected component, each can reach the other through implication paths.
Setting either literal true then forces its complement true, contradicting the requirement that xᵢ and ¬xᵢ have opposite values.
Thus, a 2-SAT instance is unsatisfiable whenever some variable and its negation belong to one strongly connected component.

28:18 Strongly Connected Components Compress Forced Values

Every literal in one strongly connected component must receive the same truth value because each reaches every other literal there.
If no component contains both xᵢ and ¬xᵢ, the remaining task is to assign truth values consistently across components.
Collapsing components produces a directed acyclic graph, so the assignment can follow its topological structure.

30:14 Complementary Components and the Source-Sink Assignment Rule

The implication graph has a complement symmetry: an edge A → B is paired with an edge ¬B → ¬A.
This pairs each strongly connected component with a complementary component in the condensation DAG.
Assigning sink components true and their complementary source components false makes the assignments compatible with implications; repeat on the remaining components.

35:39 A Linear-Time Algorithm for 2-SAT

Constructing the implication graph takes time linear in the formula size, and standard strongly connected component algorithms also run in linear time.
Reject immediately if any component contains both a literal and its negation; otherwise assign components in reverse topological order.
The resulting algorithm solves 2-SAT in O(V+E) time, which is linear in the number of literals and implication edges.

38:03 Why Max 2-SAT Escapes the Implication-Graph Algorithm

For ordinary 2-SAT, a false clause literal forces the other literal true; Max 2-SAT permits leaving a clause unsatisfied.
The implication graph therefore no longer captures mandatory consequences when the objective is to maximize the score.
A Max 2-SAT solver would also solve 2-SAT by asking whether the optimum equals the total number of clauses, but the reverse implication is not apparent.

42:29 Reducing 3-SAT to Max 2-SAT in the Correct Direction

To establish hardness, start with a known-hard 3-SAT instance and transform it in polynomial time into a Max 2-SAT instance.
A Max 2-SAT oracle must reveal whether the original 3-SAT formula is satisfiable; reducing 3-SAT to Max 2-SAT makes the latter at least as hard.
The construction first allows clauses of one or two literals, then separately converts singleton clauses into two-literal clauses.

45:35 Designing a 10-Clause Gadget for Each 3-Literal Clause

For each original clause (A ∨ B ∨ C), introduce a fresh variable Y and create 10 clauses, each with at most two literals.
The gadget includes singleton clauses A, B, C; the pair clauses (¬A ∨ ¬B), (¬B ∨ ¬C), (¬A ∨ ¬C); and four clauses involving Y.
The Y clauses are Y, (A ∨ ¬Y), (B ∨ ¬Y), and (C ∨ ¬Y); choosing Y appropriately helps separate satisfied from unsatisfied original clauses.

50:52 The Gadget’s Six-versus-Seven Score Gap

Across the eight possible truth patterns for A, B, and C, the best gadget score is 6 when all three are false.
If at least one of A, B, or C is true, an appropriate choice of Y satisfies 7 of the 10 gadget clauses.
Replacing each of m original clauses creates 10m clauses, and the optimum reaches 7m exactly when the original 3-SAT instance is satisfiable.

56:14 Proving the Reduction Threshold in Both Directions

If the 3-SAT formula is satisfiable, use its assignment and choose a suitable Y for each clause to obtain 7 points per gadget, or 7m total.
If the formula is unsatisfiable, every assignment leaves at least one original clause false; its gadget scores at most 6 while every other gadget scores at most 7.
That assignment scores at most 7m−1, so comparing the Max 2-SAT optimum with the threshold 7m decides the original 3-SAT instance.

1:05:35 Padding Singleton Clauses to Obtain Exact 2-SAT

Replace each singleton clause A with (A ∨ y) and (A ∨ ¬y), using a fresh variable y for that clause.
The replacement scores 2 when A is true and 1 when A is false, so it adds exactly one point regardless of A’s value.
With k singleton clauses, subtract the fixed offset k from the padded optimum; this completes the reduction to Max 2-SAT with exactly two literals per clause.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.