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.