完整導向圖的TSP

Question

完全有向圖上是否存在用於旅行推銷員問題的多項式時間算法？

Answer 1

不太可能。如果有一個，你可以採取任何圖形，並添加所有缺失的邊緣以非常高的重量。這將允許解決已知爲NP難題的標準版本的問題。