NP-Completeness - Proof by Restriction

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

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

StackExchange Computer Science Q#6525, answer score: 3