Polynomial-Time Reduction & NP-Completeness via 3-SAT → Vertex Cover

(i) Polynomial-Time Reduction

Many-one Karp reduction $A ≤_p B$: deterministic algorithm transforming any instance $x$ of $A$ into instance $f(x)$ of $B$ in time $poly(|x|)$ such that $x∈A ⇔ f(x)∈B$. Implies if $B∈P$ then $A∈P$; transitivity holds; $≤_p$ orders hardness.

(ii) Use to Prove NP-Completeness

To prove $B$ NP-complete: show $B∈NP$ + pick known NP-complete $A$ (e.g., 3-SAT) and show $A ≤_p B$. By transitivity every $NP$ problem reduces to $A$ reduces to $B$ → $B$ NP-hard; with $B∈NP$ → NP-complete.

(iii) Reduction 3-SAT → Vertex Cover (Sketch)

3-SAT: Conjunctive normal form with 3 literals per clause, decide satisfiability.
Vertex Cover decision: Given $G(V,E)$ and integer $k$, is there $C⊆V$, $|C|≤k$ covering all edges?

Construction: Given 3-SAT formula with $n$ vars, $m$ clauses.

• Variable gadget: For each variable $x_i$, create two vertices $x_i$, $\bar x_i$ with edge $(x_i,\bar x_i)$. Cover must pick at least one per gadget (choosing truth assignment).
• Clause gadget: For each clause $C_j = (l_a ∨ l_b ∨ l_c)$, create triangle of 3 vertices $a_j,b_j,c_j$ with edges among them. Cover must pick at least 2 of 3 per triangle.
• Connection edges: Connect each triangle vertex to its literal vertex (e.g., $a_j$ — literal $l_a$'s variable node). This forces covering choice to correspond to satisfying literal.
• Set $k = n + 2m$.

Claim: Formula satisfiable ⇔ graph has vertex cover of size ≤ $k$.

• ⇒ If assignment satisfies, pick per variable the true literal vertex, per clause pick 2 triangle vertices covering clause's false literals (at least one literal true, so the edge to its variable vertex is already covered, allowing to pick the other two triangle vertices).
• ⇐ If cover size $k$, it must use exactly 1 per variable gadget and 2 per clause triangle. Extract assignment from variable vertices in cover; each clause triangle leaves one literal uncovered → that literal's edge must be covered by its variable vertex → that literal true → clause satisfied.

Reduction is polytime ($O(n+m)$ vertices/edges). Since 3-SAT NP-complete → Vertex Cover NP-hard; clearly ∈NP (certificate = cover, verifier checks edges) → NP-complete.