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

<p>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>

<p>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.</p>

CC BY-SA 3.0
2014-04-15T09:59:23.640Z
+1: I agree that searching for a poly-time algorithm is a good starting point and reveals secrets about the problem
Helium
CC BY-SA 3.0
2014-04-15T09:15:35.613Z
2014-04-29T21:55:57.970Z
2014-04-29T21:55:57.970Z
Saeed
<p>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.</p>

<p>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, ...</p>

<p>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 <code>from -&gt; to</code> reductions of the book <a href="http://rads.stackoverflow.com/amzn/click/0716710455">Computers and Intractability: A Guide to the Theory of NP-Completeness</a>
(or other resources)
and draw a histogram of the problems in the <code>from</code> set.
Then we can find out which problems are more commonly used for reductions.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-14T21:49:45.633Z
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,..)
Marzio De Biasi
CC BY-SA 3.0
2014-04-14T23:04:55.493Z
@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.
Helium
CC BY-SA 3.0
2014-04-14T23:05:36.997Z
@MarzioDeBiasi: by the way, the list of problems that you  mentioned in your comment is useful for me too.
Helium
CC BY-SA 3.0
2014-04-15T06:51:46.660Z
I agree, but the "searching among thousands" (for a specific domain I'll say among *dozens*) is a needed phase in order to avoid a "[Reinventing-The-Wheel NPC proof](http://arxiv.org/abs/1403.3431)" (i.e. spending time proving something that is already known ... though it can be sometimes enjoyable :-). Furtehrmore if you are working on a seemingly completely new problem, then there are not too many similar problems to look at ... and probably you will soon find yourself building a reduction from scratch.
Marzio De Biasi
CC BY-SA 3.0
2014-04-15T09:42:54.760Z
@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.
Saeed
CC BY-SA 3.0
2014-04-15T15:16:23.193Z
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
<np-hardness><reductions>
NP-hardness proof: looking for some good restricted np-hard problems
Helium
# NP-hardness proof: looking for some good restricted np-hard problems

(Asked by: username_0 on 2014-04-14)

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](http://rads.stackoverflow.com/amzn/click/0716710455)
(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.

**Tags:** np-hardness, reductions

> **Comments:**
> **username_1**: 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,..)  
> **username_0**: @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.  
> **username_0**: @MarzioDeBiasi: by the way, the list of problems that you  mentioned in your comment is useful for me too.  
> **username_1**: I agree, but the "searching among thousands" (for a specific domain I'll say among *dozens*) is a needed phase in order to avoid a "[Reinventing-The-Wheel NPC proof](http://arxiv.org/abs/1403.3431)" (i.e. spending time proving something that is already known ... though it can be sometimes enjoyable :-). Furtehrmore if you are working on a seemingly completely new problem, then there are not too many similar problems to look at ... and probably you will soon find yourself building a reduction from scratch.  
> **username_2**: @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.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-04-15. Score: 6

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.

> **Comments:**
> **username_0**: +1: I agree that searching for a poly-time algorithm is a good starting point and reveals secrets about the problem  

---

