I was reading a few notes on Proof by Restriction and I am confused:

A Valid Proof by Restriction is the following:

Directed Hamiltonian Cycle Problem is NP Complete because if we look only at instances of DHC where For $G=(V,E)\quad (u,v)\in E \leftrightarrow (v,u) \in E$ then it reduces to Hamiltonian Cycle which we know is NP complete.

A wrong proof is the following:

Subset Sum problem
INSTANCE: Integers $a_1, a_2,…,a_n$ and integer B.

QUESTION: Is there a sequence of 0’s and 1’s, $x_1, x_2,…,x_n$ such that: $$\sum_{i=1}^n a_ix_i \leq B$$

is a special case of

Real Subset Problem INSTANCE: Integers $a_1, a_2,…,a_n$ and integer B.

QUESTION: Is there a sequence of real numbers $x_1, x_2,…,x_n$ such that: $$\sum_{i=1}^n a_ix_i \leq B$$

so it is NP Complete.

My notes say that the this proof is wrong since it restricts the question and not the instances but I don't seem to understand the difference.

Further, I can't really understand how Proof by Restriction works; for all I know I could be restricting an NP Complete problem to a trivial case which can be solved in Polynomial time.


migrated from cstheory.stackexchange.com Jan 14 '13 at 4:20

This question came from our site for theoretical computer scientists and researchers in related fields.


Think about the set of all possible instances of DHC. A subset of these instances are those where, for every directed edge $(u, v)$, there is always a matching directed edge $(v, u)$. (In general, this doesn't have to be the case, but it CAN be the case, which is why this is a valid restriction.)

Now think about the set of all possible instances of SubsetSum. For each such instance, you're supposed to answer with a set of 0/1-valued $x_i$. By your first definition, there are NO valid answers that include a real number in the $x_i$. So, when you suddenly allow real-valued solutions in the second version of SubsetSum, you're relaxing the problem, not restricting it. (You're giving yourself more leeway by allowing more possible solutions.)


What you have in the case of DHC is really just a reduction: assuming you could solve DHC in polynomial time, you can solve HC in polynomial time, too, because it is a special case (use the same algorithm!). Therefore, HC $\in$ NPC implies DHC $\in$ NPC.

If you think of it in terms of the usual reduction HC $\leq_p$ DHC, the polynomial transformation does nothing, so it's just a very simple reduction.

The subset sum thingy says "the special case is as hard as the general case", which is plain wrong. For example, HC is trivial on trees.


In the case of Directed Hamiltonian Cycle, when you have a solution to the restricted case (the graph with arcs going both ways), the solution is a valid solution for the original problem. In the case of subset sum, a solution to the Real Subset Sum is not a solution for the Subset Sum.

In the first case, you are showing Hamiltonian Cycle $\leq_P$ Directed Hamiltonian Cycle. In the other case, you want to say Subset Sum $\leq_P$ Real Subset Sum, and thus showing that since the latter is in $P$, the former is as well.


Your Answer

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