3SAT ≤p Vertex Cover · an NP-hardness reduction, step by step

A Karp reduction turns every instance of one problem into an instance of another, in polynomial time, so that the answers agree. Here a 3-CNF formula φ with n clauses becomes a graph G with a triangle per clause and an edge between every pair of complementary literals; the threshold is k = 2n. The page builds G, then walks through both directions of the correctness proof. Everything is live: click a literal to fix its variable, click a vertex to put it into or take it out of S.

Example

Random clauses, variables

Columns

Arrow keys step. Click a literal to make it true; click a vertex to toggle it in S.

— / — Speed 800ms

The formula φ

Click a literal to make it true (its variable is fixed accordingly); click a variable chip to cycle ? → 1 → 0. Dashed chips were chosen by the page to satisfy as many clauses as possible.

The graph G = g(φ)

(a) same clause (b) negations of each other in the cover S satisfied literal uncovered edge

What just happened

The set S

Reduction & correctness proof

Input

One clause per line, exactly three literals; a negative number is a negated variable (-3 is ¬x₃; !x3, ~x3, ¬x3 work too, and ∨, |, parentheses are ignored). Lines starting with # are comments.

# φ from the lecture
1 2 -3
-1 3 4
-1 -2 -4
2 3 4
cols 2
assign -1 -2 -3 4

cols c sets how many clause triangles go in one row; assign l₁ l₂ … presets an assignment as a list of true literals. To place a clause by hand, append @ x y to its line (grid units: one clause pitch is 1, so @ 0 0, @ 1 0, @ 0.5 1 …). Limits: 12 clauses, variables x₁…x₁₆.

Graph

Click any vertex, in any of the three pictures, to move it between S and V \ S.

Verdict

G — is S a vertex cover?

G — is V \ S an independent set?

Ḡ (complement) — is V \ S a clique?

Why the same edges light up in all three pictures

An edge {u,v} of G is uncovered by S exactly when both endpoints lie in V \ S — which is exactly when it is an edge inside V \ S, i.e. a violation of independence — which is exactly a pair of V \ S that is not adjacent in the complement Ḡ, i.e. a missing clique edge. Hence
S is a vertex cover of G ⇔ V \ S is an independent set of G ⇔ V \ S is a clique of Ḡ,
and with |V \ S| = |V| − |S| the three decision problems reduce to each other: (G, k) ∈ VertexCover ⇔ (G, |V|−k) ∈ IndependentSet ⇔ (Ḡ, |V|−k) ∈ Clique. The maps (G,k) ↦ (G, |V|−k) and G ↦ Ḡ are computable in polynomial time, so all three are NP-complete once one of them is.

Input

The usual undirected-graph format: V, then E, then one edge u v per line (vertices 0 … V−1). Optionally, after the edges, exactly V lines x y with the drawing coordinates of the vertices (any scale; the picture is fitted to the box). A line S 0 2 3 presets the set S. Lines starting with # are comments. At most 30 vertices.