Decomposing the Tour–MST Gap: An Edge-Resolved Signal for Classical and Neural TSP Solvers

We introduce a topological feedback mechanism for the Travelling Salesman Problem (TSP) by analyzing the divergence between a tour and the minimum spanning tree (MST). Our key contribution is a canonical decomposition theorem which establishes a bijection between (s,t)-tour edges and Minimum Spanning Tree edges. This theorem decomposes the classical tour-MST gap into a sum of non-negative, edge-wise topological divergence gaps derived from RTD-Lite barcodes. These gaps precisely quantify how much each edge deviates from the instance’s intrinsic multiscale cluster structure. We conduct experiments and show how the proposed topological signal improves SOTA deep learning methods for TSP: 1) fine-optimizing solutions of heatmap-based neural solvers (e.g., DIFUSCO, ATT-GCN) on large-scale instances (up to 10,000 nodes), achieving up to $14\times$ wall-clock speed-up while producing shorter tours, 2) integration into L2C leads to $0.47\%$–$0.56\%$ shorter tours. Moreover, the proposed topological guidance makes LKH, the SOTA classical method, faster by 24.1% on average across 9 hard instances while preserving overall tour quality. The proposed topological guidance also improves classical heuristics - 2-opt/3-opt. Extensive experiments demonstrate the topology-guided optimization outperforms heuristics across random Euclidean instances, TSPLIB instances, instances with non-trivial topology, non-metric TSP, asymmetric TSP, and Hamiltonian cycle problems.