<p>A classical approach to study the complexity of a problem <span class="math-container">$P$</span> is to efficiently reduce a well known problem <span class="math-container">$P'$</span> to <span class="math-container">$P$</span>, thus showing that <span class="math-container">$P$</span> is at least as difficult as <span class="math-container">$P'$</span>. The TCS literature contains thousands of such reductions.</p>
<p><strong>This induces a directed graph over problems: <span class="math-container">$P' \longrightarrow P$</span> if <span class="math-container">$P'$</span> was reduced to <span class="math-container">$P$</span>.</strong></p>
<p><strong>First question:</strong> Is there a way to collect (large parts of) this graph? Maybe web sites or publications listing many reductions in a suitable way?</p>
<p>This graph may contain interesting information on how we work, the importance of some problems, and maybe on problems themselves. For instance, problems with a very large in-degree are very often used for reductions. Cycles indicate proofs of complexity completeness. The sets of problems reduced to a same problem (the in-neighbors of this problem) may also be interesting. The out-degree of problems will be low in general, but not always, and this also brings information. The transitive links in this graph are also interesting, although trivial since reduction is transitive.</p>
<p><strong>Second question:</strong> What information shall we obtain from this graph, in your opinion?</p>
<p>Notice that I am talking of the graph of reductions <em>that have been proved in the literature</em>, not all possible reductions, which would lead to a much simpler graph because of transitivity.</p>

CC BY-SA 4.0
2021-02-15T01:14:21.573Z
Step 1 in this project is to create a database of unambiguous problem definitions.
orlp
CC BY-SA 4.0
2021-02-15T07:42:07.403Z
Sure, this is certainly a daunting task! Maybe start a collaborative wiki where each page gives a problem definition, with links to its reductions? I already see some in Wikipedia and here.
Matthieu Latapy
CC BY-SA 4.0
2021-02-15T07:52:38.097Z
Wikipedia's List of NP-complete problems (https://en.wikipedia.org/wiki/List_of_NP-complete_problems) gives a small start, and Karp's 21 NP-complete problems (https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems) give an interesting 21 vertices subgraph :)
Matthieu Latapy
CC BY-SA 4.0
2021-02-15T10:45:58.813Z
The complexity classes already form a rather messy "complexity zoo", the graph of reductions would probably be way larger (and probably involve tons of variants of problems)... Furthermore, there would have to be quite a few types of edges (polynomial reductions, fine grained reductions...). But even for Ptime reductions between NP-complete problems, I have never found online anything outside wikipedia that would match a standard textbook such as Garey Johnson. If there were a collective effort, I expect we would see more references to it in publications.
Joseph Stack
CC BY-SA 4.0
2021-02-15T10:52:53.777Z
Garey & Johnson could indeed be a good starting point since they explicitly mention for each problem from which problem the reduction is from. However I don't know how useful a graph of such reductions would be for a set of complete problems for some class, since we know that anyway all of them can be reduced to each other. I think documenting the properties of known reductions, e.g. how they affect different parameters, would be very interesting since maybe it could be used to automatically derive fine-grained results from unexpected transformations.
Laakeri
CC BY-SA 4.0
2021-02-15T16:28:11.197Z
Thank you for these relevant comments that really contribute to the question. I do agree that sub-graphs defined in some ways may make sense and be easier targets. One may for instance start with a given complexity class, or problems of a certain kind. Starting with Garey & Johnson would be great. Bibliometric tools mining citations between papers, or even between theorems, may help go further. After a first significant set of problems and reductions are collected, the hope is that colleagues will add their own reductions or their favorite ones.
Matthieu Latapy
CC BY-SA 4.0
2021-02-15T19:08:46.310Z
The compendium of NP optimization problems, by Pierluigi Crescenzi and Viggo Kann (among others) may still be an interesting source of documentation, although it has not been updated since 2005. See https://www.csc.kth.se/~viggo/problemlist/. As of the concept of reduction graph itself, I think it is interesting to see what reductions are used even among complete problems (for some class), if only to search for ideas when looking at similar problems.
Arnaud Casteigts
CC BY-SA 4.0
2021-02-16T09:35:44.537Z
@arnaud I had thought about that compendium. But it seems to me (for the samples I checked) that it does not discuss reductions.
Joseph Stack
<cc.complexity-theory><complexity-classes><soft-question><reductions><big-list>
The graph of problem reductions
Matthieu Latapy
# The graph of problem reductions

(Asked by: username_0 on 2021-02-14)

A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature contains thousands of such reductions.

**This induces a directed graph over problems: $P' \longrightarrow P$ if $P'$ was reduced to $P$.**

**First question:** Is there a way to collect (large parts of) this graph? Maybe web sites or publications listing many reductions in a suitable way?

This graph may contain interesting information on how we work, the importance of some problems, and maybe on problems themselves. For instance, problems with a very large in-degree are very often used for reductions. Cycles indicate proofs of complexity completeness. The sets of problems reduced to a same problem (the in-neighbors of this problem) may also be interesting. The out-degree of problems will be low in general, but not always, and this also brings information. The transitive links in this graph are also interesting, although trivial since reduction is transitive.

**Second question:** What information shall we obtain from this graph, in your opinion?

Notice that I am talking of the graph of reductions *that have been proved in the literature*, not all possible reductions, which would lead to a much simpler graph because of transitivity.

**Tags:** cc.complexity-theory, complexity-classes, soft-question, reductions, big-list

> **Comments:**
> **username_1**: Step 1 in this project is to create a database of unambiguous problem definitions.  
> **username_0**: Sure, this is certainly a daunting task! Maybe start a collaborative wiki where each page gives a problem definition, with links to its reductions? I already see some in Wikipedia and here.  
> **username_0**: Wikipedia's List of NP-complete problems (https://en.wikipedia.org/wiki/List_of_NP-complete_problems) gives a small start, and Karp's 21 NP-complete problems (https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems) give an interesting 21 vertices subgraph :)  
> **username_2**: The complexity classes already form a rather messy "complexity zoo", the graph of reductions would probably be way larger (and probably involve tons of variants of problems)... Furthermore, there would have to be quite a few types of edges (polynomial reductions, fine grained reductions...). But even for Ptime reductions between NP-complete problems, I have never found online anything outside wikipedia that would match a standard textbook such as Garey Johnson. If there were a collective effort, I expect we would see more references to it in publications.  
> **username_3**: Garey & Johnson could indeed be a good starting point since they explicitly mention for each problem from which problem the reduction is from. However I don't know how useful a graph of such reductions would be for a set of complete problems for some class, since we know that anyway all of them can be reduced to each other. I think documenting the properties of known reductions, e.g. how they affect different parameters, would be very interesting since maybe it could be used to automatically derive fine-grained results from unexpected transformations.  
> **username_0**: Thank you for these relevant comments that really contribute to the question. I do agree that sub-graphs defined in some ways may make sense and be easier targets. One may for instance start with a given complexity class, or problems of a certain kind. Starting with Garey & Johnson would be great. Bibliometric tools mining citations between papers, or even between theorems, may help go further. After a first significant set of problems and reductions are collected, the hope is that colleagues will add their own reductions or their favorite ones.  
> **username_4**: The compendium of NP optimization problems, by Pierluigi Crescenzi and Viggo Kann (among others) may still be an interesting source of documentation, although it has not been updated since 2005. See https://www.csc.kth.se/~viggo/problemlist/. As of the concept of reduction graph itself, I think it is interesting to see what reductions are used even among complete problems (for some class), if only to search for ideas when looking at similar problems.  
> **username_2**: @arnaud I had thought about that compendium. But it seems to me (for the samples I checked) that it does not discuss reductions.  

---

## 0 answers

