# How to reduce to an NP-hard problem?

For an assignment I have to program an application to schedule conversations. There is an event where representatives of the elementary schools talks with the representatives of high schools. They will talk about the students that will be transferred to the highschool. There are approximately 200 elementary schools and 40 high schools that will be participating in this event. The schools already know which student is transferring to which high school. The conversations will only be between representatives of E and H from student that will be transferring to H.

The rules are:

1. The duration of each conversation is based on the amount of students per representatives.Each conversation last 5 minutes per student. If a group consist of 1 student, this conversation last 10 minutes.
2. No timeclashes
3. All the students of the same group will be scheduled together, so, a representatives will only face the same representative once.
4. Timespan is 13.00-19.00
5. The waiting time of a representative is at most 20% of his time. A waiting time is an empty timeslot between the 1st and last conversation.
6. Schedules for 2 days
7. Each representatives participate for 1 day.

The problem is that I know that this is hard to solve, but I dont know if it's NP-hard. Right now I only know this problem is similar to a Job Shop Problem. What can I do to proof that my problem is NP-hard? I read that I need to reduce a known problem to my problem. But how do I do this? I have read different articles and books, but I still don't understand the steps to do it.

## 2 Answers

Just an extended comment.

I think that before trying to find a reduction, you should try to better formalize the problem:

• define exactly what the parameters of the problem are, formalize their constraints, and formalize the question;
• try to simplify (or remove) the details;

For example:

• If a group consist of 1 student, this conversation last 10 minutes. $\rightarrow$ it is equivalent to a group of two students, so you can remove it;

• Timespan is 13.00-19.00 $\rightarrow$ in the other rules you use minutes, so convert the "timespan" to $T$ minutes;

• try to think if a simplified version of the problem has a quick solution or it can be still hard (e.g. if the event last only one day rules 7 and 8 can be dropped)

• express the rules with a math formula: e.g "if an elementary group $E$ of $n$ students talk with a high school group $H$ of $m$ students then the total time $TT$ required is $TT(E,H)=....$"; "the total max wait time $WT$ for group $E$ is $WT = ...$"

Furthermore there is a point that it is not clear (to me):

• suppose you have an elementary school group $E$ having $n$ students that talk with a high school group $H$ having $m$ students; what is the total time required? (1) $5 * n$ (the talk is public) or (2) $5 * ( n / m)$ (each student of E talks with a single student of H). If the talk is public, then the number of students is redundant, and you can think only in terms of total time required by a school group.
• The talk only between the 2 reps. – Nico Liu Sep 6 '12 at 11:10
• If I simplify the problem like you said: if the event last only 1 day. Wouldn't the problem be harder to solve? And what should be the next step of this? – Nico Liu Sep 6 '12 at 11:14
• @NicoLiu: you should think about the generalization of the problem (if you think about a single particular instance the notion of "NP-hardness" is meaningless); and don't confuse the hardness of the problem with the "chances" of finding a valid solution. From the computational complexity perspective, a decision problem can be easy because no valid solution exists at all (the answer is always "no" on all inputs). – Vor Sep 6 '12 at 12:32
• @NicoLiu: And what should be the next step of this: you can follow the steps listed in rphv's answer, but if you feel unfamiliar with the "terms" used (decision problem, polynomial time, NP-complete, reduction, ...) then perhaps you need to learn more on complexity theory before trying to apply it (you can ask here for books/lectures/...). Otherwise, if you know well those terms, edit the question and make it more concise/formal (start with changing the title which is not correct :-), and you'll probably receive a more specific/detailed answer. – Vor Sep 6 '12 at 12:59
• @NicoLiu: ... perhaps another evidence that you should rewrite the question in a more formal way :-) ... – Vor Sep 6 '12 at 15:39

Garey & Johnson outline the following four steps for proving NP-completeness results:

1. Show that your problem is in NP. Informally, this means that it's possible to verify the correctness of potential solutions to your problem "quickly" - i.e., in polynomial time.
2. Select a known NP-complete problem. Again, Garey & Johnson provide an excellent list. They suggest that 3SAT, 3-Dimensional Matching, Vertex Cover, Clique, Hamiltonian Circuit, and Partition "...can serve as a 'basic core' of known NP-complete problems for the beginner."
3. Construct a reduction from the known NP-complete problem to your problem. Very informally, to construct such a reduction one might first assume the existence of a "black box" which quickly solves instances of your problem. Then, demonstrate that it's possible to quickly solve the known NP-complete problem selected in step 2 using your "black box." This implies that your problem is "at least as hard" as a known NP-complete problem. Finally, to show that your problem is "no harder" than an NP-complete problem, proceed in the opposite direction: start with a "black box" that solves the NP-complete problem, and show that you can quickly solve your problem using that box.
4. Show that the reduction in step 3 is a polynomial reduction. In other words, show that the "black box" solutions in step 3 take place in polynomial time.
• 1. is only necessary if you want NP-completeness, which Nico does not seem to need. – Raphael Sep 5 '12 at 19:53
• A proof of NP-hardness (as opposed to NP-completeness) can also leave off everything after "Finally..." in step 3. – rphv Sep 5 '12 at 20:33
• The problem is that I'm not trained to be a scientist. So it is hard for me to come up with different formula to proof this. I have read the theory about it. But I don't know what I have to reduce. In the book 'Computational Complexity' by Christos H. Papadimitriou, there is a way called reduction by generalization. My question is does it mean that I can say (Without the formula) that a Job is the elementary school, Machine the high school and Operation is the conversation. While explaining that the constraints are the same. – Nico Liu Sep 6 '12 at 9:26
• @rphv aren't (1) and (3) after finally rendundant? Both show the problem to be in NP. Supposing we did want to show the problem was NP-complete and not just NP-hard, we should only need to do one or the other. (1) is often easier. "(3) after finally" is often still an instructive exercise, however. As an aside, doing the last half of (3) instead of the first half, i.e. reducing the wrong way is a mistake newcomers to NP-completeness proofs sometimes make. – Joe Sep 7 '12 at 19:21
• @Joe I believe you're right - anything "easier" than NP-complete is in NP. – rphv Sep 8 '12 at 5:42