Proof by restriction: when is it valid to restrict to a special case?

Question

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.

Answer 1

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.)

Answer 2

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.

Answer 3

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.