Can you turn the TSP into a graph isomorphism problem?

Question

Let's say you found a way to solve graph isomorphisms in polynomial time, so far I am aware that you can solve all cases using László Babai's algorithm in quasi-polynomial time.

Are you able to transform the traveling salesman problem into a graph isomorphism?

Answer 1

I will assume that by 'transform into' you mean a polynomial time reduction.

According to Wikipedia, it is not known whether the graph isomorphism problem is NP complete or not.

If there is a polynomial time reduction from TSP to the graph isomorphism problem, then the graph isomorphism problem is NP complete, since TSP is NP complete.

In conclusion, we don't know.

Answer 2

There is considerable evidence that Graph Isomorphism (GI) is not $\textsf{NP}$-complete. So I would be surprised if there was a $\textsf{P}$-computable reduction from TSP to GI.

• If GI is $\textsf{NP}$-complete, then the Polynomial-Hierarchy collapses to $\textsf{PH} = \Sigma_{2} \cap \Pi_{2} = \textsf{AM}$ (the last equality is again a consequence of the collapse and is not known to be true).
• GI is in the low hierarchy of $\textsf{NP}$. So GI is unlikely to be $\textsf{NP}$-complete, as again $\textsf{PH}$ would collapse (https://www.sciencedirect.com/science/article/pii/0022000088900104?via%3Dihub).
• GI is low for $\textsf{PP}$ and $\textsf{C=P}$. This is not known to be true for any $\textsf{NP}$-complete problem (https://link.springer.com/article/10.1007/BF01200427)
• If GI is $\textsf{NP}$-complete, then $\textsf{NP} \subseteq \textsf{DTIME}(n^{\text{poly} \log n})$, which implies that $\textsf{EXP} = \textsf{NEXP}$. It is widely believed that $\textsf{EXP} \neq \textsf{NEXP}$. (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.2228&rep=rep1&type=pdf)
• The decision and counting variants of GI are equivalent. This is not known to be the case for any $\textsf{NP}$-complete problem (https://www.sciencedirect.com/science/article/abs/pii/0020019079900048).