4
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Step 1 in this project is to create a database of unambiguous problem definitions. $\endgroup$
    – orlp
    Commented Feb 15, 2021 at 1:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joseph Stack
    Commented Feb 15, 2021 at 10:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Laakeri
    Commented Feb 15, 2021 at 10:52
  • 1
    $\begingroup$ 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 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. $\endgroup$
    – Arnaud Casteigts
    Commented Feb 15, 2021 at 19:08
  • 1
    $\begingroup$ @arnaud I had thought about that compendium. But it seems to me (for the samples I checked) that it does not discuss reductions. $\endgroup$
    – Joseph Stack
    Commented Feb 16, 2021 at 9:35

0

Reset to default

Your Answer

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