Hilbert–Krylov Tower Decomposition for the Traveling Salesman Problem: Exact-Verified Solutions with Reduced Effective Complexity | IJCT Volume 12 – Issue 6 | IJCT-V12I6P68
International Journal of Computer Techniques
ISSN 2394-2231
Author
Michael S. Yang
Abstract
We apply the Hilbert–Krylov Tower Decomposition (HKD), previously introduced for Subset Sum, to the Traveling Salesman Problem (TSP). Without modifying the underlying NP-hard formulation, HKD is used as a structured pruning mechanism over the classical Held–Karp dynamic programming state space. On geometrically structured Euclidean in- stances, HKD recovers tours that match the exact Held–Karp optimum while exploring orders of magnitude fewer state expansions. This paper presents a concise experimental demonstration and a fully reproducible reference implementation.
Keywords
^KEYWORDS^
Conclusion
This experiment demonstrates that HKD can collapse the effective complexity of an exact NP- hard dynamic programming algorithm by orders of magnitude on structured instances, while preserving global optimality as verified by comparison with Held–Karp on tractable problem sizes.
Together with the Subset Sum result in [1], this supports the view that HKD defines a general-purpose structural complexity reduction framework applicable across distinct NP-hard domains.
References
[1] M. S. Yang, Hilbert–Krylov Tower Decomposition and a Pseudo-Polynomial Complexity Bound for Subset Sum, International Journal of Computer Techniques, vol. 12, no. 6, 2025. https://ijctjournal.org/hilbert-krylov-pseudo-polynomial-complexity/
How to Cite This Paper
Michael S. Yang (2025). Hilbert–Krylov Tower Decomposition for the Traveling Salesman Problem: Exact-Verified Solutions with Reduced Effective Complexity. International Journal of Computer Techniques, 12(6). ISSN: 2394-2231.
