Counting Locally Optimal Tours in the TSP

Bodo Manthey, Jesse van Rhijn

We show that the problem of counting the number of 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show…