Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916792049336320 |
|---|---|
| author | Gutekunst, Samuel C. |
| author_facet | Gutekunst, Samuel C. |
| contents | We study the edge-length polytope, motivated both by algorithmic research on the Circulant Traveling Salesman Problem (Circulant TSP) and number-theoretic research related to the Buratti-Horak-Rosa conjecture. Circulant TSP is a special case of TSP whose overall complexity is a significant still-open question, and where on an input with vertices $\{1, 2, ..., n\}$, the cost of an edge $\{i, j\}$ depends only on its length $\min\{|i-j|, n-|i-j|\}$. The edge-length polytope provides one path to solving circulant TSP instances, and we show that it is intimately connected to the factorization of $n$: the number of vertices scales with $n$ whenever $n$ is prime and with $n^{3/2}$ whenever $n$ is a prime-squared, but there are a superpolynomial number of vertices whenever $n$ is a power of 2. In contrast, the more-standard Symmetric TSP Polytope has roughly $n!$ vertices. Hence, for Circulant TSP, a brute-force algorithm checking every vertex is actually efficient in some cases, based on the factorization of $n$. As an intermediate step, we give superpolynomial lower-bounds on two combinatorial sequences related to the Buratti-Horak-Rosa conjecture, which asks what combinations of edge lengths can comprise a Hamiltonian path. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_10758 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds Gutekunst, Samuel C. Discrete Mathematics Data Structures and Algorithms Combinatorics We study the edge-length polytope, motivated both by algorithmic research on the Circulant Traveling Salesman Problem (Circulant TSP) and number-theoretic research related to the Buratti-Horak-Rosa conjecture. Circulant TSP is a special case of TSP whose overall complexity is a significant still-open question, and where on an input with vertices $\{1, 2, ..., n\}$, the cost of an edge $\{i, j\}$ depends only on its length $\min\{|i-j|, n-|i-j|\}$. The edge-length polytope provides one path to solving circulant TSP instances, and we show that it is intimately connected to the factorization of $n$: the number of vertices scales with $n$ whenever $n$ is prime and with $n^{3/2}$ whenever $n$ is a prime-squared, but there are a superpolynomial number of vertices whenever $n$ is a power of 2. In contrast, the more-standard Symmetric TSP Polytope has roughly $n!$ vertices. Hence, for Circulant TSP, a brute-force algorithm checking every vertex is actually efficient in some cases, based on the factorization of $n$. As an intermediate step, we give superpolynomial lower-bounds on two combinatorial sequences related to the Buratti-Horak-Rosa conjecture, which asks what combinations of edge lengths can comprise a Hamiltonian path. |
| title | Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2506.10758 |