NP-Completeness - Proof by Restriction

Question

I'm reading Garey & Johnsons "Computers and Intractability" and I'm at the part "Some techniques for solving NP-Completeness". Here's the text about Proof by Restriction:

Proof by restriction is the simplest, and perhaps most frequently applicable, of our three proof types. An NP-completeness proof by restriction for a given problem $L \in NP$ consists simply of showing that $L$ contains a known NP-complete problem $L'$ as a special case. The heart of such a proof lies in the specification of the additional restrictions to be placed on the instances of $L$ so that the resulting restricted problem will be identical to $L'$. We do not require that the restricted problem and the known NP-complete problem be exact duplicates of one another, but rather that there be an "obvious" one-to-one correspondence between their instances that preserves "yes" and "no" answers."

And I'm trying to learn this technique by example, but need some help.

(If you have the book, my example is on page 65, 27th printing)

They prove that Multiprocessor Scheduling is NP-complete with the following proof:

(Paraphrasing):

Restrict to PARTITION by allowing only instances in which $m = 2$ and $D$ $=$ half the total sum of the "lengths".

Here $m$ is the number of processors and $D$ is the maximum allowed sum of "lengths" per processor.

This is obviously a special case of multiprocessor scheduling which is solvable by solving the PARTITION problem, and there's no confusion there.

But, I'm not sure why this proof holds.

Excerpt from above: "The heart of such a proof lies in the specification of additional restrictions to be placed on the instances of $L$ so that the resulting restricted problem will be identical to $L'$ ".

The way I see it that means we have to find the special case, and then find restrictions that show us that this problem can always be reduced to the special case. What we're trying to do here is show that Problem $A$ (MS) is at least as hard as Problem $B$ (PARTITION), so why would a simple special case be enough here? Is it because there's an obvious way to map to this special case that I'm missing? Or perhaps because $m = 1$ is trivial and we know that the problem will only get harder with a higher $m$, and that $D$ is always arbitrary, therefore $A$ must be at least as hard as $B$ (I feel like I'm just guessing now :p)

I hope it is clear where I get lost.

TLDR; Why is it enough to find a special case that is solvable by an NP-Complete problem? Don't we need some reduction to complete the proof?

Answer 1

There is an implicit (trivial) reduction, from each instance of the restricted version to itself, really just relabelling it as an instance of the unrestricted problem.

To give an example that I think is more illuminating than Partition and Multiprocessor Scheduling, we can look at Vertex Cover and Hitting Set:

Vertex Cover
Input: A graph $G=(V,E)$, a positive integer $k$.
Question: Is there a set $V'\subset V$ of size at most $k$ such that for every $uv \in E$ either $u\in V'$ or $v\in V'$ or both?

Hitting Set
Input: A hypergraph $H=(X,E)$, a positive integer $k$.
Question: Is there a subset $X'\subseteq X$ of size at most $k$ such that for every $e \in E$ there exists an $x \in X'$ such that $x \in e$?

So we can easily see that Vertex Cover is just Hitting Set where the size of the edges is exactly two. As Vertex Cover is NP-hard (indeed, complete), Hitting Set must also be NP-hard. As Hitting Set is also in NP, it is therefore NP-complete.

So we have a "reduction" from Vertex Cover to Hitting Set, but it's just the identity mapping. The graph remains unchanged (as does $k$), we just call it a hypergraph, and call the edges hyperedges.

To think about it from the other end, if we have a problem $\Pi$ where a restricted subproblem $\Pi'$ is already NP-hard, and we had a PTIME algorithm for $\Pi$, then we could use it to solve all the instances of $\Pi'$ in polynomial time and hence everything in NP would have a polynomial time algorithm. Thus $\Pi$ must be NP-hard (and if $\Pi \in$ NP, NP-complete).