Counting Locally Optimal Tours in the TSP

Bodo Manthey; Jesse van Rhijn

doi:10.4230/LIPIcs.MFCS.2025.73

Counting Locally Optimal Tours in the TSP

Bodo Manthey^*
, Jesse van Rhijn^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Downloads (Pure)

Abstract

We show that the problem of counting 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is O(1.2098ⁿ√n!). Based on numerical experiments, we conjecture that the true bound is at most O(√n!), which is approximately the square root of the total number of tours.

Original language	English
Title of host publication	50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025
Editors	Pawel Gawrychowski, Filip Mazowiecki, Michal Skrzypczak
Place of Publication	Dagstuhl
Publisher	Dagstuhl
ISBN (Electronic)	9783959773881
DOIs	https://doi.org/10.4230/LIPIcs.MFCS.2025.73
Publication status	Published - 20 Aug 2025
Event	50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025 - University of Warsaw, Warsaw, Poland Duration: 25 Aug 2025 → 29 Aug 2025 Conference number: 50 https://mfcs2025.mimuw.edu.pl/

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Publisher	Schloss Dagstuhl - Leibniz Center for Informatics
Volume	345
ISSN (Print)	1868-8969

Conference

Conference	50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025
Abbreviated title	MFCS 2025
Country/Territory	Poland
City	Warsaw
Period	25/08/25 → 29/08/25
Internet address	https://mfcs2025.mimuw.edu.pl/

Keywords

2-opt
heuristics
local search
probabilistic analysis
Travelling salesman problem

Access to Document

10.4230/LIPIcs.MFCS.2025.73Licence: CC BY

ArticleFinal published version, 945 KBLicence: CC BY

Cite this

@inproceedings{574d23170e0e46d9a85c4ae7a7dbb589,

title = "Counting Locally Optimal Tours in the TSP",

abstract = "We show that the problem of counting 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is \#P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is O(1.2098n√n!). Based on numerical experiments, we conjecture that the true bound is at most O(√n!), which is approximately the square root of the total number of tours.",

keywords = "2-opt, heuristics, local search, probabilistic analysis, Travelling salesman problem",

author = "Bodo Manthey and \{van Rhijn\}, Jesse",

note = "Publisher Copyright: {\textcopyright} Bodo Manthey and Jesse van Rhijn.; 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, MFCS 2025 ; Conference date: 25-08-2025 Through 29-08-2025",

year = "2025",

month = aug,

day = "20",

doi = "10.4230/LIPIcs.MFCS.2025.73",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Dagstuhl",

editor = "Pawel Gawrychowski and Filip Mazowiecki and Michal Skrzypczak",

booktitle = "50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025",

address = "Germany",

url = "https://mfcs2025.mimuw.edu.pl/",

}

Manthey, B & van Rhijn, J 2025, Counting Locally Optimal Tours in the TSP. in P Gawrychowski, F Mazowiecki & M Skrzypczak (eds), 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025., 73, Leibniz International Proceedings in Informatics, LIPIcs, vol. 345, Dagstuhl, Dagstuhl, 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, Warsaw, Poland, 25/08/25. https://doi.org/10.4230/LIPIcs.MFCS.2025.73

Counting Locally Optimal Tours in the TSP. / Manthey, Bodo ; van Rhijn, Jesse.
50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025. ed. / Pawel Gawrychowski; Filip Mazowiecki; Michal Skrzypczak. Dagstuhl: Dagstuhl, 2025. 73 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 345).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Counting Locally Optimal Tours in the TSP

AU - Manthey, Bodo

AU - van Rhijn, Jesse

N1 - Conference code: 50

PY - 2025/8/20

Y1 - 2025/8/20

N2 - We show that the problem of counting 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is O(1.2098n√n!). Based on numerical experiments, we conjecture that the true bound is at most O(√n!), which is approximately the square root of the total number of tours.

AB - We show that the problem of counting 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is O(1.2098n√n!). Based on numerical experiments, we conjecture that the true bound is at most O(√n!), which is approximately the square root of the total number of tours.

KW - 2-opt

KW - heuristics

KW - local search

KW - probabilistic analysis

KW - Travelling salesman problem

UR - https://www.scopus.com/pages/publications/105014727230

U2 - 10.4230/LIPIcs.MFCS.2025.73

DO - 10.4230/LIPIcs.MFCS.2025.73

M3 - Conference contribution

AN - SCOPUS:105014727230

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025

A2 - Gawrychowski, Pawel

A2 - Mazowiecki, Filip

A2 - Skrzypczak, Michal

PB - Dagstuhl

CY - Dagstuhl

T2 - 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025

Y2 - 25 August 2025 through 29 August 2025

ER -

Counting Locally Optimal Tours in the TSP

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Counting Locally Optimal Tours in the TSP

Cite this