1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ That was a +1 immediately after the first line in your answer. $\endgroup$ – Hendrik Jan Sep 21 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.