VC ≤p SUBSET-SUM | Complexity Atlas

The construction

The idea. Build numbers you can picture as rows of a table: one special column $d$ , plus one column per edge. A vertex row "reports" which edges it touches; an edge row is a unit vector. The target demands exactly $2$ in every edge column and exactly $K$ in column $d$ . The trick: "exactly $2$ " is satisfiable iff at least one endpoint of the edge was chosen.

The algorithm. On input $G=(V,E)$ and $K\in\mathbb N$ , write $m=|E|$ and $E=\{e_1,\dots,e_m\}$ :

If $K>|V|$ , replace $K$ by $|V|$ .
For each $v\in V$ a number $a_v$ of $m+1$ digits: the leftmost digit is $1$ , and digit $j+1$ is $1$ if $v\in e_j$ , else $0$ .
For each $e\in E$ a number $a_e$ of $m+1$ digits: the leftmost is $0$ , and digit $j+1$ is $1$ iff $e=e_j$ .
A target $S$ : its leftmost digits encode $K$ , and every remaining digit is $2$ .
Return the list $\{a_v\}\cup\{a_e\}$ and $S$ .

Algebraically: $a_v=10^{m}+\sum_{j=1}^{m}[\,v\in e_j\,]\cdot10^{\,m-j},\qquad a_{e_i}=10^{\,m-i},\qquad S=K\cdot10^{m}+\sum_{j=1}^{m}2\cdot10^{\,m-j}.$

About step 0. $\mathrm{VC}$ asks for a cover of size at most $K$ , while the construction forces exactly $K$ in column $d$ . The gap is harmless: (a) adding vertices to a cover keeps it a cover, so a cover of size $\le K$ with $K\le|V|$ can be padded to exactly $K$ ; (b) if $K>|V|$ then $(G,K)\in\mathrm{VC}$ always, so the replacement does not change the answer.

Visualization

G = P₅: |V| = 5, m = |E| = 4K = 3

Vertex number a_v

One row per constructed number; one column for d and one for each edge; the last rows give the column totals and the target.
number	d	e₁	e₂	e₃	e₄	value

Step 0 — at most K becomes exactly KIf K > |V| replace K by |V|. A cover of size ≤ K always pads up to size exactly K, so forcing K in column d is harmless.

Correctness — both directions

VC ∈ ⟹ SUBSET-SUM ∈

Lemma 4.1 (no carrying) — the step without which nothing works. Let $I$ be any subset of the constructed numbers, write $U=I\cap\{a_v\}$ (identified with a vertex set) and for each $j$ $c_j=\bigl|\{v\in U:v\in e_j\}\bigr|+[\,a_{e_j}\in I\,].$ Then (1) $0\le c_j\le3$ ; (2) $\sum_{x\in I}x=|U|\cdot10^m+\sum_j c_j 10^{m-j}$ , and this is exactly the decimal representation — the addition carries in no edge column; (3) $\sum_j c_j10^{m-j}<10^m$ .

Proof. (1) The edge $e_j$ has exactly two endpoints, so at most two vertex numbers carry a $1$ in column $j$ , plus exactly one edge number; the column total is $\le3$ . (2) Expand and group by powers of $10$ ; each $c_j\le3\le9$ is a legal digit, so nothing carries left. (3) $\sum_j 3\cdot10^{m-j}=\frac{10^m-1}{3}<10^m$ . $\square$

Corollary 4.2 (the digit criterion). $\sum_{x\in I}x=S$ iff $|U|=K$ and $c_j=2$ for every $j$ . Proof of $\Rightarrow$ : write $L=\sum_j c_j10^{m-j}$ and $L'=\sum_j2\cdot10^{m-j}$ , both in $[0,10^m)$ . The hypothesis gives $(|U|-K)\cdot10^m=L'-L$ , whose right side is smaller than $10^m$ in absolute value while the left is an integer multiple of $10^m$ — so both vanish. $\square$

The direction. Suppose $(G,K)\in\mathrm{VC}$ ; after step 0, $K\le|V|$ , so there is a cover $U\subseteq V$ with $|U|=K$ exactly. Put $I_1=\{a_u\mid u\in U\}$ .

In column $d$ each contributes $1$ , and exactly $K$ vertices were chosen — contribution $K$ , exactly as in $S$ .

Fix $j$ . As $U$ is a cover, at least one endpoint of $e_j$ lies in $U$ ; and as there are only two endpoints, at most two. So the column total is $1$ or $2$ .

Define $I_2$ : for every $j$ whose column came to $1$ , add $a_{e_j}$ . That number adds $1$ to column $j$ alone and $0$ everywhere else (including $d$ ), so it "repairs" $1$ to $2$ without disturbing anything. It cannot repair $0$ to $2$ — and that is exactly right: the value $0$ cannot occur here, precisely because $U$ is a cover.

So $c_j=2$ for every $j$ and $|U|=K$ , and by Corollary 4.2 the numbers in $I_1\cup I_2$ sum to exactly $S$ .

SUBSET-SUM ∈ ⟹ VC ∈

Suppose some subset $I$ of the constructed numbers sums to exactly $S$ . As in Lemma 4.1, write $U=I\cap\{a_v\}$ (identified with a vertex set). By Corollary 4.2, $|U|=K,\qquad c_j=\bigl|\{v\in U:v\in e_j\}\bigr|+[\,a_{e_j}\in I\,]=2\quad\text{for every }1\le j\le m .$

Fix $j$ . The term $[\,a_{e_j}\in I\,]$ is at most $1$ , since there is exactly one number for the edge $e_j$ and it can be picked at most once. Hence $\bigl|\{v\in U:v\in e_j\}\bigr|=2-[\,a_{e_j}\in I\,]\;\ge\;1 .$

So every edge $e_j$ has at least one endpoint in $U$ , i.e. $U$ is a vertex cover of $G$ . Its size is $|U|=K\le K$ , so $(G,K)\in\mathrm{VC}$ .

Cost of the reduction

TimeO(|x|²)

SpaceO((|V| + m)·m)

Output sizeO((|V| + m)·m + log K) digits

One loop over the vertices and one over the edges, writing an $(m+1)$ -digit number for each, plus $S$ . Testing " $v\in e_j$ " is $O(1)$ with adjacency lists, so computation time is proportional to output size.

A remark made only in passing, and the heart of the lesson: the value of every constructed number is of order $10^{m}$ — exponential in the input size. This is not a problem, because the reduction must run in polynomial time and writing such a number costs only $m+1$ digits. The reduction is legal precisely because it may produce numbers of enormous value with a modest encoding length — the same value-versus-length distinction, seen from its other side.

What it buys

$\mathrm{SUBSET\text{-}SUM}$ is NP-complete. From here the numeric chain continues: $\mathrm{SUBSET\text{-}SUM}\le_p\mathrm{PARTITION}\le_p\mathrm{BIN\text{-}PACKING}$ .

Pitfalls

Without the no-carry lemma there is no proof. Had any column total reached $10$ , it would carry a $1$ leftward, and a correct-looking total could arise from an entirely wrong combination of columns — ten $1$ s in one column "impersonating" a $1$ in its neighbour. The whole argument rests on equal sums forcing equality digit by digit. (Any base $\ge4$ would do; base $10$ is chosen purely for legibility.)
$K$ is written as a block of digits, not one digit. The number of chosen vertices $|U|$ may be $10$ or more, and then the leftmost "digit" is not a digit. The argument in Corollary 4.2 assumes nothing about $|U|$ — it only exploits that anything below $10^m$ stays below $10^m$ .
The reduction builds numbers from the graph and $K$ alone and never looks for a cover. The same "grave sin" rejected in $\mathrm{3COL}\le_p\mathrm{4COL}$ recurs here: the construction must never be phrased in terms of the solution.

The chain

Rests on

IS ≤p VC

Used later by

SUBSET-SUM ≤p PARTITION

Where this was read from

Lesson 11משפט 4 (לב השיעור): $\mathrm{VC} \le_p \mathrm{SUBSET\text{-}SUM}$
Guided exercisesubset-sum-encoding

The $\Leftarrow$ direction is absent from the written summary and was given orally in the lecture with the remark "if you really want to feel you understand this — write it out". The write-up here is that completion.