# NP-hardness proof: looking for some good restricted np-hard problems

To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can be used for the reduction, but in practice, some of the problems are more easily reduced than others.

For instance, 3-SAT is usually a better choice for constructing a reduction than SAT because the former one is more restricted than the latter one, 3-partition is usually an easier choice than bin packing, ...

One way to find such "good" problems for the reduction is to do a statistical analysis over the existing reductions. E.g., one can shape all the pairs of from -> to reductions of the book Computers and Intractability: A Guide to the Theory of NP-Completeness (or other resources) and draw a histogram of the problems in the from set. Then we can find out which problems are more commonly used for reductions.

I wonder if such a statistical analysis makes sense at all. Has such a research been already conducted or not? If not, what is your guess about the most commonly used problems for reductions.

The reason I am asking this question is that I have already done a few proofs of NP-hardness, but almost all of them rely on reduction from the same problem (3-partition). I am looking for other options to use in my proofs.

• From my small experience, I think that it depends on the domain of the problem you are facing (arithmetic,graph theory, scheduling, puzzles,..); first of all you should look for similar or related NPC problems to see if there is a good problem to start FROM (e.g. A1-A12 classif. of G&J); then look at their NPC proofs to get hints/insights on the direction you can follow; finally if nothing comes out try to use simple "low-level" NPC problems that don't require complex structures (3SAT,1 in 3 SAT,Planar SAT,Exact Cover by Three Sets, 3-coloring,3-partition,Ham cycle in planar or grid graphs,..) Apr 14 '14 at 21:49
• @MarzioDeBiasi: You are right but I think searching among thousands of problems to find the proper one is an exhausting job. The ranking based on the number of reductions that I suggested gives us a clue about where to start our search from. In fact, we don't usually pick a problem just randomly. We usually pick the problem based on similarity (is that a good word?) and based on frequency of reductions that we have already seen from that problem. I just wanted to make this selection a bit more formal or at least get some advice from the experts in the area about their favorite problems. Apr 14 '14 at 23:04
• @MarzioDeBiasi: by the way, the list of problems that you mentioned in your comment is useful for me too. Apr 14 '14 at 23:05
• @MarzioDeBiasi, I think it's very nice if you share your experiences as an answer, you are one of the bests about hardness proofs in cstheory.SE. Apr 15 '14 at 9:42
• listen closely to MDB re G&J. they organize problem types into sections. there are maybe thousands of NP complete problem variants but they are in basic themes/genres/sections. a large graph would be interesting to construct but its not really statistical. it probably exibits small world structure where there are key "hubs". G&J themselves list the primary hubs in different chapters/sections.
– vzn
Apr 15 '14 at 15:16