Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
Note that the mentioned technique only shows NP-hardness, not NP-completeness! The NP-part is missing. (G&J are a tad unclear/sloppy there.) –  Raphael Nov 7 '12 at 10:32
    
@Raphael Noted. My comment on the answer below did take that into account. And yes, they seem to find that part of the proof redundant in a lot of cases :p –  ᴋᴇʏsᴇʀ Nov 7 '12 at 10:35
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
And I understand the implicit trivial reduction, I just don't understand how it relates to the proof being complete. Thinking about it from the other end really helped, but maybe you could clarify the first part anyway? –  ᴋᴇʏsᴇʀ Nov 7 '12 at 14:35
    
Except that you haven't proved that the subset of $\Pi$ that isn't $\Pi'$ is actually in NP, which means you haven't shown that you can solve those remaining instances with the NP-complete language $\Pi'$. –  Ben Nov 7 '12 at 22:31
    
@Keyser, the reduction only actually shows hardness, the completeness you prove seperately, though it is usually a very simple proof; a problem is in NP if you can check a given solution in polynomial time, so for example, we can check a solution to Hitting Set by simply checking that the solution actually does touch all the edges, so Hitting Set is in NP. Then that along with the fact that Vertex Cover is a restricted case gives NP-completeness. –  Luke Mathieson Nov 8 '12 at 0:00
    
@Ben, it's true that the restriction just shows hardness, see the above comment or the extra bits I put in the answer. However, we aren't trying to show that we can solve $\Pi-\Pi'$ with $\Pi'$, we showing that if we had a PTIME algorithm for $\Pi$ it immediately gives a PTIME algorithm for $\Pi'$ (the same algorithm). After the proof is finished and we show that they're both complete, then we can say that we could (in principle) use an algorithm for $\Pi'$ to solve instances in $\Pi-\Pi'$, but it doesn't use the reduction in the proof. –  Luke Mathieson Nov 8 '12 at 0:04
    
Thanks for answering Luke. Not sure I follow though. I understand the concept NP-hard+in NP->NP-complete (and I said NP-hard? :p). I've worked with VC/HS too and I have the exact same problem there (I do fully understand the reductions though). So,since a P-solution to HS implies a P-solution for VC, HS is NP-hard. Makes sense :p But isn't my claim correct then? (The one in the first comment). Also, I don't see how the "identity mapping" tells us anything about HS except that VC is fully contained within it. For me,it's like you skip a step when you say "Hitting Set must also be NP-hard" –  ᴋᴇʏsᴇʀ Nov 8 '12 at 0:55
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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