Concrete example of Vertex Cover to Subset Sum reduction
In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem...


We do?


  ... mostly to prove Subset Sum is NP-Complete.


There's no particular reason to go down that route. Karp&nbsp;[1] defined the Knapsack problem as: given $a_1, \dots, a_r, b\in\mathbb{Z}$, is there a set $S\subseteq \{1, \dots, r\}$ such that $\sum_{i\in S}a_i=b$? This is one variant of what is now called Subset Sum. If you prefer to define Subset Sum such that $b$&nbsp; is always zero, we'll come back to that in a minute.

Karp shows that Subset Sum is NP-complete by the chain of reductions
$$\text{SAT}\leq \text{3SAT} \leq \text{Chromatic Number}\leq\text{Exact Cover}\leq\text{Subset Sum}\,.$$
In particular, the reduction from Exact Cover to Subset Sum produces an instance where the $a_i$'s and&nbsp;$b$ are all positive so, if you want to define Subset Sum as "is there a subset whose total is zero?", you can set $a_{r+1}=-b$.

Since Subset Sum and Vertex Cover are both NP-complete, there is clearly a reduction between them. However, you shouldn't expect that there's a "nice" reduction where a small VC instance naturally transforms into a small Subset Sum instance that makes you say, "Aha, now I understand." And that applies to most pairs of NP-complete problems.  In complexity theory courses, we teach the simple, intuitive reductions, usually between problems that are somehow similar, or between SAT or 3SAT and a problem that isn't about Boolean formulas. That can give the impression that there's a natural reduction between any pair of NP-complete problems; in reality, there usually isn't.



[1] Richard M. Karp, Reducibility among combinatorial problems. In Complexity of Computer Computations, Plenum Press, 1972. (PDF)