8
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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,..) $\endgroup$
    – Marzio De Biasi
    Apr 14, 2014 at 21:49
  • $\begingroup$ @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. $\endgroup$
    – Helium
    Apr 14, 2014 at 23:04
  • $\begingroup$ @MarzioDeBiasi: by the way, the list of problems that you mentioned in your comment is useful for me too. $\endgroup$
    – Helium
    Apr 14, 2014 at 23:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – Saeed
    Apr 15, 2014 at 9:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – vzn
    Apr 15, 2014 at 15:16

1 Answer 1

Reset to default
6
$\begingroup$

I don't know if there is a machinery way to do this, but my little personal experience works as follows.

I try to provide a polynomial time algorithm for a problem. In those tries usually I can see there are some restricted versions of problem which are polynomial time solvable. I also will understand what part of my algorithm was handwaving for original problem. I can compare this two cases (difference between restricted versions and the general one also the part of an algorithm which was hard to improve). By comparing those two cases usually it's possible to guess how does the problem bottleneck looks like. So we can find a related hard problem. Usually providing an algorithm for a problem is hard job, and needs good knowledge about a problem. After we get this knowledge about the problem we can have many different ideas to tackle problem in different scenarios (not just hardness results).

P.S: If your proof relays on a particular problem, I think it's because that problem is very close to your work, so don't blame yourself.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ +1: I agree that searching for a poly-time algorithm is a good starting point and reveals secrets about the problem $\endgroup$
    – Helium
    Apr 15, 2014 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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