Menu
Does there exist a polynomial time algorithm for Travelling Salesman Problem on complete directed graph?
586
asked Oct 20 '25 22:10
Unlikely. If there was one you could take any graph and add all the missing edges with a very high weight. That would allow solving the standard version of the problem, which is known to be NP-hard.
162
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
