<p>You may find this classic textbook useful: Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael Garey and David S. Johnson.</p>
<p><a href="https://en.wikipedia.org/wiki/Computers_and_Intractability" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Computers_and_Intractability</a></p>

CC BY-SA 4.0
2020-08-11T21:20:20.667Z
2020-08-11T21:20:20.667Z
Mahdi Cheraghchi
<p>I'm interested in tables of which problems are reducible to which other problems. Particularly for graph problems, but any such tables/graphs would be neat, just so I know how to look for them. Professors in lectures used to draw them on the blackboard, but I can't seem to find them in literature.</p>

CC BY-SA 4.0
2020-08-10T14:34:57.810Z
Technically, all $\mathsf{NP}$-complete problems have (polynomial time) reductions between each other. If we introduce some sort of natural reduction graph, one could start at [Karp's 21 problems](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems).
Watercrystal
CC BY-SA 4.0
2020-08-10T16:35:03.290Z
*Thousands* of problems have been considered in the literature, hence this is too broad a request to be answerable. Also, *tables* seem an odd and counterintuitive way of conveying this information. I’m not even sure what such a table would look like; you mean an adjacency matrix of the reducibility relation with +/- entries, or something else? Usually, reducibilities among multiple problems are depicted using a Hasse diagram instead, such as in https://www.math.ucdavis.edu/~greg/zoology/diagram.xml (though this particular diagram is for complexity classes rather than individual problems).
Emil Jeřábek
CC BY-SA 4.0
2020-08-12T01:15:14.577Z
Also look in, e.g., CLRS intro algorithm's text, or Sipser's theory of computation text.
Neal Young
<cc.complexity-theory>
tables of reductions in literature
Gurkenglas
# tables of reductions in literature

(Asked by: username_0 on 2020-08-10)

I'm interested in tables of which problems are reducible to which other problems. Particularly for graph problems, but any such tables/graphs would be neat, just so I know how to look for them. Professors in lectures used to draw them on the blackboard, but I can't seem to find them in literature.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Technically, all $\mathsf{NP}$-complete problems have (polynomial time) reductions between each other. If we introduce some sort of natural reduction graph, one could start at [Karp's 21 problems](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems).  
> **username_2**: *Thousands* of problems have been considered in the literature, hence this is too broad a request to be answerable. Also, *tables* seem an odd and counterintuitive way of conveying this information. I’m not even sure what such a table would look like; you mean an adjacency matrix of the reducibility relation with +/- entries, or something else? Usually, reducibilities among multiple problems are depicted using a Hasse diagram instead, such as in https://www.math.ucdavis.edu/~greg/zoology/diagram.xml (though this particular diagram is for complexity classes rather than individual problems).  
> **username_3**: Also look in, e.g., CLRS intro algorithm's text, or Sipser's theory of computation text.  

---

## 1 answers

### Answer by username_4 on 2020-08-11. Score: 1

You may find this classic textbook useful: Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael Garey and David S. Johnson.

<https://en.wikipedia.org/wiki/Computers_and_Intractability>


---

