2
$\begingroup$

I was looking at the wikipedia page for the Travelling Salesman Problem and found a reference to another exact algorithm besides Held-Karp that's also $O(2^nn^2)$.

Specifically: "This bound has also been reached by Exclusion-Inclusion in an attempt preceding the dynamic programming approach."

Can you explain how that algorithm works?

$\endgroup$

1 Answer 1

2
$\begingroup$

The quoted sentence is inaccurate. There is a known inclusion-exclusion algorithm for the Hamiltonian path problem i.e. unweighted TSP. The algorithm can be extended to the integer-weighted case, but the runtime and space depend linearly on the maximum distance $W$ between two cities, which is exponentially large in general.

The difference between weighted and unweighted cases is often confused because sometimes "Hamiltonian path" and "TSP" are used interchangeably. The Wikipedia article mainly covers the weighted TSP.

See "Exact Exponential Algorithms" Chap.4.2.2 [1] for details of the inclusion-exclusion algorithm. The book states "the existence of a polynomial space algorithm solving the TSP problem in time $O^\ast(2^n)$ is an interesting open problem".

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.