In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line of - A graph G has VC of size k if and only if there is a subset S that sums exactly to t. However, not able to find out (understand) exactly what is this t. I think providing a concrete example will help many like me. Request any one to provide a concrete graph with |VC| 3 or something manageable, and then show exact value of t i.e. what would be the exact instance of subset sum problem. Finally, explaining/clearly mentioning elements of S would be of great help.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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 [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$ 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 $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)
answered Sep 21 '19 at 8:56
-
$\begingroup$ That was a +1 immediately after the first line in your answer. $\endgroup$ – Hendrik Jan Sep 21 '19 at 16:13
