Exercises — NP-complete problems — 3-SAT, Vertex Cover, Clique, Hamiltonian Path, TSP, Subset Sum

Answer: (b). A certificate must be something you can verify in polynomial time. Given a list of $k$ vertices, you check every one of the $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ pairs is an edge — that is fast. Option (a) is just the input, it proves nothing. Option (c) is part of the input. Option (d) is an unsupported claim — you cannot check it. This is the core of NP: easy to check, apparently hard to find.

False. The target $t$ is a number. Its input length is ${\log }_{2}t$ bits, so $t$ itself can be as large as $2^{(\text{bits})}$ — exponential in the input size. An algorithm costing $O(n\cdot t)$ is therefore exponential in the input length. We call this pseudo-polynomial. Subset Sum is genuinely NP-complete; the hardness hides in problems whose numbers are large.

You reduce a known hard problem into Vertex Cover ($\text{KnownHard}{\le }_p\text{VertexCover}$). Feed the monster to the problem you want to prove hard. If instead you reduced Vertex Cover into something easy, you'd only prove Vertex Cover is easy — the opposite of what you want.

We found a minimum vertex cover of size 3 in a graph with $n=5$ vertices. By the duality identity, the complement of a minimum cover is a maximum independent set of size $n-3=2$. Concretely, complement of $\{a,c,d\}$ is $\{b,e\}$. Check: is edge $be$ present? The cycle edges are $ab,bc,cd,de,ea$ — no $be$. So $\{b,e\}$ has no internal edge → independent. ✔ Largest independent set has size $2$. (See Graph Theory — Cliques and Independent Sets.)

Budget $B=n=4$ (a tour visits all $n$ vertices and returns, using exactly $n$ edges; cheapest possible is $n$ real edges of weight 1). Tour $a\to b\to c\to d\to a$ uses edges $ab,bc,cd,da$. Each is in $E$ → weight $1$ each. Total $=1+1+1+1=4=B$. ✔ Since the cost equals the budget, this tour uses only real edges, so it corresponds exactly to a Hamiltonian cycle in the original graph.

• $x_1$–$\neg x_2$? negation pair → no edge.
• $x_1$–$\neg y_2$? ok → edge. $x_1$–$z_2$? ok → edge.
• $y_1$–$\neg y_2$? negation pair → no edge.
• $y_1$–$\neg x_2$? edge. $y_1$–$z_2$? edge.
• $\neg z_1$–$z_2$? negation pair → no edge.
• $\neg z_1$–$\neg x_2$? edge. $\neg z_1$–$\neg y_2$? edge. Clique of size 2? Pick one vertex per clause that are joined. E.g. $\{x_1,z_2\}$: edge present → clique. Set $x=\text{true}$ (satisfies clause 1) and $z=\text{true}$ (satisfies clause 2). Consistent (no variable forced both ways) → satisfiable. ✔ (Many valid cliques exist, e.g. $\{y_1,\neg x_2\}$ giving $y=\text{true},x=\text{false}$.)

The size-$m$ clique is meant to encode "one true literal from each of the $m$ clauses." Because there are no intra-clause edges, a clique can contain at most one vertex per clause; to reach size $m$ it must take exactly one from each. If we added intra-clause edges, a clique could grab two literals of the same clause and skip another clause entirely — then the clique no longer represents "one satisfied literal per clause," and satisfiability is no longer captured. The missing edges are what force the one-per-clause structure.

Columns: [var $x$ | clause $C$] — 2 digits, base 10.

• $T=11$ (i.e. value $11$): a $1$ in the $x$-column (variable chosen), and a $1$ in the $C$-column because $x$ appears positively in $C$.
• $F=10$ (value $10$): a $1$ in the $x$-column, $0$ in $C$ ($x$ does not appear negatively in $C$).
• Slack numbers for clause $C$: $s_1=01$ (value $1$) and $s_2=02$ (value $2$).
• Target $t=13$ (value $13$): variable column $=1$ (pick exactly one of $T/F$), clause column $=3$ (needs $\ge 1$ literal contribution). Find the subset: to hit clause-column $3$ we need literal-contribution $\ge 1$, so we must pick $T$ (which gives $1$ in the $C$-column). $T=11$. Remaining to reach $13$: $13-11=2$, use slack $s_2=2$. Subset $\{T,s_2\}=\{11,2\}$ sums to $13=t$. ✔ This says $x=\text{true}$, which indeed satisfies $C=(x)$. (Alternatively $\{T,s_1,...\}$ — but $11+1=12\ne 13$; $11+2=13$ is the clean hit. $F=10$ can never reach clause-column 3 with only slacks $1,2$ since $10+1+2=13$ but that would need both slacks AND leaves clause col $=0+1+2=3$ ✔ yet variable col $=1$ ✔ — wait that also works with $F$! Check: does it correspond to a satisfying assignment? $F$ means $x=$false, then $C=(x)$ is FALSE. But the slacks $1+2=3$ fake the clause. This is exactly why the max slack must be $2$ and target clause-digit $3$ with clauses of 3 literals — with a 1-literal clause the encoding degenerates; the real construction uses 3-literal clauses so slack alone can add at most $2<3$ and cannot fake satisfaction. Our toy is intentionally showing the boundary.)

Let $|V|=n$, and let $I\subseteq V$ with $C=V\setminus I$ (so $|C|=n-|I|$). Key fact: $C$ is a vertex cover $⟺$ $I$ is an independent set. Proof of the fact:

• ($\Rightarrow$) Suppose $C$ covers every edge. Take any edge $uv$. Since $C$ covers it, at least one of $u,v$ is in $C$, i.e. not both are in $I$. So no edge has both endpoints in $I$ → $I$ is independent.
• ($\Leftarrow$) Suppose $I$ is independent. Take any edge $uv$. Both endpoints cannot be in $I$ (else $I$ has an internal edge), so at least one endpoint is outside $I$, i.e. in $C$. So $C$ covers every edge. Now the sizes: $G$ has an independent set of size $\ge k$ $⟺$ its complement (a vertex cover) has size $\le n-k$. This is a reduction in both directions, so the two problems are equivalent, and either one being NP-complete makes the other NP-complete. ✔

Construction. Given $G=(V,E)$, $n=|V|$. Build complete graph $K_n$ on $V$ with $w(u,v)=\{\begin{array}{ll}1& (u,v)\in E\\ 2& (u,v)\notin E\end{array},B=n.$ This is computable in poly time ($O(n^2)$ edges). Now prove correctness. ($\Rightarrow$) $G$ has a Hamiltonian cycle $\Rightarrow$ tour cost $\le n$. The Hamiltonian cycle visits all $n$ vertices, using $n$ edges, all of which are in $E$, hence weight $1$ each. Total $=n\cdot 1=n=B$. ✔ ($\Leftarrow$) tour cost $\le n\Rightarrow G$ has a Hamiltonian cycle. Any tour uses exactly $n$ edges. Each edge costs $\ge 1$, so cost $\ge n$. Combined with cost $\le n$, cost $=n$, forcing every edge to cost exactly $1$, i.e. every tour-edge is in $E$. A tour visiting all vertices once using only $E$-edges is a Hamiltonian cycle in $G$. ✔ Both directions hold, so $\text{HamCycle}{\le }_p\text{TSP}$. Since Ham Cycle is NP-complete, so is TSP.

Yes. With only two weight values, $1$ and $2$: the left side $w(u,v)$ is at most $2$, and the right side $w(u,x)+w(x,v)$ is at least $1+1=2$. So $w(u,v)\le 2\le w(u,x)+w(x,v)$ always holds. Hence this reduction already produces a metric TSP instance, proving metric TSP is NP-complete too — which is why metric TSP is studied via Approximation Algorithms (e.g. the Christofides $1.5$-approximation) rather than exact poly-time solvers.

Two things to prove: in NP, and NP-hard. (A) Vertex Cover ∈ NP. Certificate = the set of $\le k$ vertices. Verify in poly time: check its size, then check every edge has an endpoint in the set ($O(|E|)$). ✔ (B) Vertex Cover is NP-hard. Reductions compose: since $\text{3-SAT}{\le }_p\text{Clique}$ (translator $f$) and $\text{Clique}{\le }_p\text{VertexCover}$ (translator $g$), the composition $g\circ f$ is a poly-time translator with $x\in \text{3-SAT}⟺g(f(x))\in \text{VertexCover}$. Poly $\circ$ poly is poly. So $\text{3-SAT}{\le }_p\text{VertexCover}$. Because 3-SAT is NP-hard (every NP problem reduces to it via Cook–Levin Theorem then to 3-SAT), transitivity gives: every NP problem ${\le }_p$ Vertex Cover. So Vertex Cover is NP-hard. (A)+(B) $\Rightarrow$ Vertex Cover is NP-complete. ∎

The runtime $O(2^k\cdot n)$ is not polynomial in the input size in general — it is exponential in the parameter $k$. Two points:

1. $k$ can be as large as $n$ (e.g. asking for a cover of size $n/2$), giving $2^{n/2}\cdot n$ — exponential.
2. An algorithm of the form $f(k)\cdot n^{O(1)}$ is called fixed-parameter tractable (FPT). FPT is a real and useful notion, but "polynomial in input size for fixed small $k$" is not the same as "polynomial for all inputs." Proving P = NP would require an algorithm polynomial in the total input length with no exponential factor in any parameter that can grow. ✔ The claim confuses parameterized tractability with unconditional polynomial time.

Idea. Vertex Cover asks to touch every edge; Dominating Set asks to touch every vertex. Bridge them: to make "cover every edge" become "dominate every vertex," turn each edge into a vertex that must be dominated. Construction. Given $G=(V,E)$ (VC instance, parameter $k$), build $G^{\prime }$: keep all vertices $V$. For each edge $e=uv\in E$, add a new vertex $w_e$ joined to both $u$ and $v$. (Also, to handle isolated original vertices you connect... — see subtlety.) Ask for a dominating set of size $\le k$ in $G^{\prime }$. Why it works ($\Rightarrow$). A vertex cover $C$ of size $k$ in $G$: every edge $uv$ has an endpoint in $C$, which is adjacent to $w_{uv}$, so $w_{uv}$ is dominated; original vertices are dominated because each has an incident edge whose covering endpoint is a neighbour (or itself). $C$ dominates all of $G^{\prime }$. The subtlety. A dominating set in $G^{\prime }$ might choose a subdivision vertex $w_e$ instead of an original endpoint, which does not correspond to a vertex cover. Fix: replace each single $w_e$ by a small triangle gadget (connect $u$, $v$, and $w_e$ into a triangle), or route the domination so that choosing an original endpoint is always at least as good — forcing the dominating set to prefer real vertices. This care in "removing spurious solutions" is exactly the $\Leftarrow$-direction discipline from L4. ✔