acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 wall-clock speed-up while producing shorter tours, 2) integration into L2C leads to – 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.

Primary area:
optimization
Keywords:
Travelling Salesman Problem, Topological Data Analysis, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_sbb5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces an improvement heuristic for TSP solvers. The core idea is to use an edge-wise topological divergence measurement over the decompositional gap between a TSP tour and the minimum spanning tree, then the larger divergence will be used for local search.

Critical strengths
  1. The paper introduces a novel heuristic of topological data analysis in combinatorial optimization.

  2. The theoretical analysis is valuable for an interpretable signal of guiding local search.

  3. The paper introduces extensive experiments and shows reasonable improvements.

Critical weaknesses
  1. The LKJ results are promising. However, in the abstract and main body of the paper, the reported aggregated speedup is 24.1%, but in Appendix U, it is 21.4%.

  2. The L2C integration results show very incremental improvement over small and moderate-sized instances, not to mention that the instances are synthetic instances. It would be great to see some comparison with other inexpensive region-selection strategies such as prioritizing long tour edges, high local costs, or different types of geometric measures.

  3. The abstract is cherry-picking the results. The abstract says that p is smaller than 10^{-3} but in Table 3 for the 2000-node instance, p is 0.028.

  4. The paper mentioned multiple times that the work is applicable to ATSP and HCP setting but the experiements largely reduce the problem to symmetric setting and use the same optimization methods. More evidence on how the proposed methods can be used for fundamentally different combinatorial optimization problems instead of symmetric TSP need to provided.

Questions for authors

Please see weakness and addresses the questions there.

3 comments
AuthorsOpenReview ↗

Response to Reviewer sbb5

W1. On LKH improvement.

24.1% instead of 21.4% is a typo. We are fixing abstract/main text in the revision.

W2. On L2C gains and inexpensive region-selection baselines.

Prioritizing long tour edges performs similarly to uniform region selection (the difference is not statistically significant), whereas RTDL-guided selection improves the gap by 0.47–0.56 percentage points. We are adding new experimental results to the revision.

nL2C gap (%)L2C + Long tour edges gap (%)L2C + RTDL gap (%)Δ Long edges / win-ratep-value Long edgesΔ RTDL / win-ratep-value RTDL
5003.3643.3392.8050.026 / 46%0.550.559 / 70%7.2 × 10⁻⁴
20006.8916.9606.420−0.070 / 33%0.700.471 / 60%2.8 × 10⁻²

W3. On the p-value the Introduction.

You are correct about the p-value statement. The main text says p<10−3p<10^{-3} for the L2C result, but Table 3 reports p=7.21×10−4p=7.21 \times 10^{-4} for n=500, p=2.8×10−2p=2.8 \times 10^{-2} for n=2000. We are replacing p<10−3p<10^{-3} with p<0.05p<0.05 in the Introduction, in the paper’s revision.

W4. On ATSP/HCP scope.

The current ATSP/HCP experiments are proof-of-concept via the Jonker-Volgenant symmetric reduction, as stated in Section 4.3, and they do show gains in solution quality, including HCP-200 exact solutions increasing from 1.0% to 7.0% and HCP-500 from 0.0% to 13.0%. We agree this does not establish a fundamentally new asymmetric or HCP-specific algorithm. We are narrowing the claim: the method applies to weighted graphs and can be used after standard reductions, but the paper's main empirical evidence is for symmetric TSP and TSP-based neural pipelines.


Concluding remarks. We hope these additional experiments address the Reviewer's concerns regarding L2C region-selection. We welcome any further questions and would appreciate reconsideration of the overall rating in light of the new evidence.

It is good to see that the typos are fixed, and the claims are more accurate. The additional experiments are helpful. But the issue claimed contribution with the previous results remain the same.

We thank the Reviewer for verifying the corrections. Regarding the remaining concern that the contribution over previous results is incremental, we make the delta precise:

  1. Versus the strongest previous results. Heatmap-based neural solvers (DIFUSCO, SoftDist, DIMES, UTSP, ATT-GCN): RTDL-enhanced post-processing shortens tours on every instance (p<10−8p < 10^{-8}, win rates 70-99%) and cuts post-processing wall-clock by up to ~14× at (n=10410^{4}) (DIMES: 112.7h → 8.0h, Table 4) - with pretrained checkpoints. Against NeuroLKH (leading learned candidate model): faster in 180/180 matched-budget paired runs, ~18% better average tour length on hard (n=1000-5000) instances, under both uniform and mixed training. Against FastT2T post-processing: shorter tours and ~2× less wall-clock at n=500, 1000 (see response to Reviwer VGWK). Against LKH-3: 21.4% aggregate CPU reduction at preserved quality.

  2. Versus prior edge priors. Existing priors (α\alpha-nearness, learned candidate sets, heatmaps) are instance-dependent: they score edges by likelihood of appearing in some good tour. RTDL is the first tour-dependent signal, scoring how badly an edge violates the cluster structure of the current solution. This enables plug-in use with any pretrained solver (six frameworks, no retraining), and sees edges static priors structurally cannot: α\alpha-nearness provably protects the inter-cluster bridge needed for the optimum in Appendix U.1 (stock LKH: 9/15 seeds; RTDL-biased: 12/15). We also prove α\alpha-nearness is a degenerate RTDL bar (Prop. 3.5) with p(e)≥α(e)p(e) \ge \alpha(e), a strict generalization of LKH's 25-year-old candidate signal.

  3. Versus RTD-Lite. RTD-Lite proves a pairing exists and intervals sum to an aggregate cost difference - but nothing about which edge receives which penalty. The edges bijection alone does not give a valid per-edge signal: Appendix X exhibits Gale's rank-matching, which satisfies the same sum yet penalizes MST edges that provably cannot contribute to suboptimality. Our new guarantees - the zero-penalty law p(e)=0  ⟺  e∈E(Tmst),p(e) = 0 \iff e \in E(T_{mst}), stability under ties and perturbations, and the lower bound L(tour)≥L(MST)+w(e^)L(\text{tour}) \ge L(\text{MST}) + w(\hat e) make the barcode an edge-wise penalty, and have no counterpart in RTD-Lite.

If the Reviewer believes a specific delta is smaller than claimed, we would be grateful to know which, and will address it with additional evidence. Otherwise, given the correctness issues are resolved and the contribution is demonstrated in matched comparisons against the strong previous results, we respectfully ask the Reviewer to consider raising the score.

Reviewer_VGWKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper constructs a connectivity-based pairing between the edges of a spanning tour path and an instance MST. The resulting nonnegative weight differences decompose the path-MST cost gap and are interpreted through RTD-Lite barcodes. The authors use these tour-dependent edge scores to order local-search moves, guide reconstruction in frozen neural solvers, and modify LKH. Experiments include Euclidean and non-metric TSP, TSPLIB, transformed ATSP/HCP, neural heatmap post-processing up to 10,000 nodes, and L2C reconstruction. The paper additionally claims tie-independent per-edge scores, a dominance relation to alpha-nearness, and a policy-invariant reward-shaping interpretation.

Critical strengths
  1. The paper turns a global tour-MST gap into useful local search guidance. The nonnegative path-edge decomposition motivates a tour-dependent score that can guide classical and frozen neural solvers without retraining.

  2. The signal shows practical value across several solver families. Heatmap post-processing improves tour quality, L2C reduces the explosion-500 gap from 3.364% to 2.805%, and the LKH study reports runtime gains over 20 matched seeds on nine hard instances. These results support utility beyond a single solver.

Critical weaknesses
  1. The theoretical advance over RTD-Lite is unclear, and the stronger guarantees need correction. RTD-Lite [1] already gives the edge pairing, nonnegative intervals, and the MST-cost-difference identity. Theorem 3.1 appears to specialize these results to a tour and the instance graph. Moreover, the counterexamples in Questions 2-3 contradict the claimed tie-independent edge scores and unrestricted alpha-nearness dominance. The remaining contribution is mainly the use of these scores in TSP search.

  2. The practical advantage over strong solvers is not established. The largest speedups are relative to plain 2-opt, while the LKH gains cover nine hard instances and the L2C gains vary by distribution. A compact matched-budget comparison with a strong classical alternative, such as GA-EAX [2] or restarted LKH with POPMUSIC [3], and a relevant neural search baseline, such as NeuroLKH [4] or Fast-T2T [5], would clarify the contribution. The current results do not show a consistent quality-runtime advantage over strong solvers.

[1] Eduard Tulchinskii, Daria Voronkova, Ilya Trofimov, Evgeny Burnaev, and Serguei Barannikov. RTD-Lite: Scalable Topological Analysis for Comparing Weighted Graphs in Learning Tasks, AISTATS, 2025.

[2] Yuichi Nagata and Shigenobu Kobayashi. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. INFORMS Journal on Computing, 2013.

[3] Jonathan Heins, Lennart Schäpermeier, Pascal Kerschke, and Darrell Whitley. Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem. International Conference on Parallel Problem Solving from Nature, 2024.

[4] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem. NeurIPS, 2021.

[5] Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization. NeurIPS, 2024.

Questions for authors

Please see the weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer VGWK, part 1/2

W1. Relation to RTD-Lite and theoretical claims.

We agree that RTD-Lite provides the barcode machinery. Tulchinskii et al. 2025 study a general case of two graphs RTD-Lite (A, B). Our intended theoretical contribution is the specialization of RTD-Lite that turns the tour-vs-instance comparison into a tour-edge penalty with an exact decomposition of LT−LMSTL_{T} - L_{MST}. The essential contribution is turning this decomposition into a dynamically recomputed, tour-dependent edge priority, rather than using RTD-Lite as a scalar comparison or training loss. Starting from a single weighted TSP instance (G) and a Hamiltonian cycle (C), we construct the tour graph (A=C), assigning infinite weight to absent edges, and compare it with (B=G), using the same, unnormalized edge weights. The obtained tour-MST bijection ψ:E(Ttour)→E(TMST∖emax)\psi: E(T_{tour}) \to E(T_{MST} \setminus e_{max}) and penalties p(e)=w(e)−w(ψ(e))p(e) = w(e) − w(\psi(e)) has attractive properties:

  1. p(e)=0⇔e∈E(TMST)p(e) = 0 \Leftrightarrow e \in E(T_{MST}), which justifies using p(e)p(e) as an edge penalty. A general rank-order edge bijection doesn’t have this property (Appendix X).
  2. stability of per-edge penalties under ties and perturbations (Appendix D)
  3. LKH's α\alpha-nearness is recovered as a degenerate RTDL bar (Proposition 3.5)
  4. p(e)≥α(e)p(e) \ge \alpha(e), the difference is p(e)p(e) is tour-dependent
  5. the new tour length lower bound L(Ttour)≥L(Tmst)+w(e^)L(T_{tour})\geq L(T_{mst})+w(\hat{e}) (Proposition 3.4)

Crucially, the resulting guidance is not equivalent to ranking edges by distance or static α\alpha-nearness. In the TSP-200 ablation (Table 12), RTDL ordering achieves length 11.356 versus 11.750 for α\alpha-nearness and 11.780 for distance ordering. For frozen L2C, prioritizing long edges provides no significant improvement, whereas RTDL reduces the optimality gap from 3.364% to 2.805% (Table 25). These comparisons support the additional information supplied by the tour-conditioned signal.

W1. On tie-independence of edge scores and unrestricted alpha-nearness dominance

Tie-independence of edge scores follows from the stability of the RTDL-Barcode (Proposition 3.2b, Appendix F). We discuss it in Section 3, in the “Note on duplicate weights” paragraph. Counterexamples in Questions 2-3 are not visible to us. We invite Reviewer to post them, and we will respond point-by-point within the discussion period.

W2. On strong baselines.

Our current claim is not that RTDL dominates all strong solvers as a standalone method. It is that a training-free, tour-dependent topological signal improves several solver families when inserted into their inference/search loops.

  1. The strongest evidence for wall-clock utility is not against plain 2-opt alone. The modification LKH+RTDL (Appendix U) over 9 hard instances and 20 matched seeds each, is faster in 180/180 paired runs than LKH, with 21.4% average CPU reductions and mean tour-length change of -0.107%. This is a matched-seed quality-runtime result on a strong classical solver, not only a 2-opt speedup.

  2. NeuroLKH. We have tested NeuroLKH across nine hard instances (Appendix U, Fig. 14), three small instances for matched time budgets. We observed that NeuroLKH behaves significantly worse than the LKH+RTDL, probably because the learned candidate model does not transfer to these hard clustered topologies, regardless of training distribution . On small sized problems it converges to optimal solution but on hard problems of size 1000+ it’s 16% (NeuroLKH, uniform), and 20% (NeuroLKH_M, mixed) worse on average than the LKH+RTDL. We are adding these experimental results to Appendix U.

instancenbudget, secLKH-3.0.14 RTDLNeuroLKH (uniform)NeuroLKH_M (mixed)
H5000a500015005,259,9276,655,0086,995,608
H5000b5000150049,438,49752,987,08553,156,127
H5000c5000150026,494,35031,222,14131,371,824
H3000a30009003,532,6374,726,2984,866,515
H3000b300090014,775,00918,574,20518,374,008
H2000b20006008,212,6868,224,34211,437,590
H2000c20006005,564,2396,146,6256,165,039
H2000d200060019,542,85321,978,22221,355,459
H100010003001,307,2071,618,1791,393,363
C32783011,49911,49911,499
C2260307,3487,3487,348
C2142306,9446,9446,944
AuthorsOpenReview ↗

Response to Reviewer VGWK, part 2/2

  1. FastT2T. 2-opt (+ RTDL) applied to tours via Fast-T2T heatmaps greedy decoding. Average over 3 runs of Fast-T2T heatmaps. 2-opt+RTDL is better in both length and wall-clock time
TSP-500TSP-1000TSP-10000
LengthTimeLengthTimeLengthTime
Greedy17.69 ± 0.062.23 ± 0.07 (m)24.84 ± 0.019.03 ± 0.2 (m)91.82 ± 0.123.38 ± 0.08 (h)
+ 2-opt16.84 ± 0.01+ 0.58 ± 0.06 (m)23.58 ± 0.02+ 4.94 ± 0.18 (m)74.58 ± 0.08+ 25.71 ± 1.82 (h)
+ 2-opt + RTDL16.78 ± 0.02+ 0.44 ± 0.01 (m)23.45 ± 0.01+ 2.51 ± 0.05 (m)73.44 ± 0.03+ 3.28 ± 0.2 (h)

We are adding new experimental results with FastT2T, NeuroLKH to a revision (a paragraph in Appendix U, Table 26).


Concluding remarks. We hope these additional experiments address the Reviewer's concerns regarding strong baselines. We welcome any further questions and would appreciate reconsideration of the overall rating in light of the new evidence.

Thank you for the clarification and additional comparisons.

The new results strengthen the empirical evidence. However, the theoretical contribution still appears to be primarily a specialization of existing RTD-Lite results, with the main advance lying in its application to TSP search. So, I maintain my Weak Reject recommendation.

Reviewer_T2NNOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposed a topological divergence gap to measures how much each each edge contributes to the tour's sub-optimality relative to the instance's minimum spanning tree (MST) for solving the traveling salesman problem (TSP). The proposed signal does not require a retraining of a learning-based optimization method and can be incorporate into the test-time solving or decoding process. The paper validated the approach across multiple size of TSP instances, demonstrating that the signal can help find better quality solution within shorter iterations.

Critical strengths
  • The proposed topological divergence gap is training free and can be incorporated into a learning-based method without additional training.
  • The approach does not rely on training date to calibrate the parameters.
Critical weaknesses
  • The paper seems to better fit an OR journal that seeks theoretical advancement in TSP.
  • The experiments lack the report of computational overhead to support the real-world implementation.
Questions for authors
  1. While the paper highlights the limitations of existing methods, several baselines, particularly learning-based methods, fail to report performance relative to total wall-clock runtime. Reporting improvements on a per-iteration basis can be misleading and may introduce bias.
  2. The authors should include a comparison with NeuroLKH, as it also aims to accelerate LKH by identifying promising edge moves candidates.
  3. Please provide a formal definition of "RTDL" upon its first mention.
  4. The proposed method relies on the computation of the Minimum Spanning Tree (MST). While this is a relatively efficient operation, does the work account for the MST computation time in the reported wall-clock latency?
  5. In Table 5, no comparison with Concorde is provided even for the small TSPLib instances.

NeuroLKH: Neurolkh: Combining deep learning model with lin-kernighan-helsgaun heuristic for solving the traveling salesman problem. NeurIPS 2021

3 comments
AuthorsOpenReview ↗

Reponse to Reviewer T2NN

W1. On venue fit.

The paper is not primarily an OR-theory result. The ICLR contribution is an inference-time structural signal that improves frozen learned solvers (L2C, INViT, five heatmap solvers) without retraining, with theory explaining why the signal is meaningful. Subject areas of ICLR include optimization, learning on graphs and other geometries & topologies.

W2, Q1. The experiments lack the report of computational overhead to support the real-world implementation.

Our main experimental results in Tables 1, 2, 4, 5 report total wall-clock time both for baselines and the proposed method. Table 4 separates neural heatmap generation from local-search time and includes RTDL computation in the 2-opt+RTDL time. For example, at TSP-10000, DIFUSCO post-processing drops from 31.23h to 3.85h, ATT-GCN from 78.08h to 6.97h, DIMES from 112.73h to 7.99h, and SoftDist from 23.4h to 6.89h, while tours are also shorter. Appendix U similarly reports LKH+RTDL over 20 matched seeds on 9 hard instances, with 180/180 paired runs faster and 13.36% to 34.72% CPU reduction. We are adding a remark in Section 4.2, Appendix Z.

Q2. On comparison with NeuroLKH.

We have tested NeuroLKH across nine hard instances (Appendix U, Fig. 14), three small instances for matched time budgets. We observed that NeuroLKH behaves significantly worse than the LKH+RTDL, probably because the learned candidate model does not transfer to these hard clustered topologies, regardless of training distribution . On small sized problems it converges to optimal solution but on hard problems of size 1000+ it’s 16% (NeuroLKH, uniform), and 20% (NeuroLKH_M, mixed) worse on average than the LKH+RTDL. We are adding these experimental results to Appendix U.

instancenbudget, secLKH-3.0.14 RTDLNeuroLKH (uniform)NeuroLKH_M (mixed)
H5000a500015005,259,9276,655,0086,995,608
H5000b5000150049,438,49752,987,08553,156,127
H5000c5000150026,494,35031,222,14131,371,824
H3000a30009003,532,6374,726,2984,866,515
H3000b300090014,775,00918,574,20518,374,008
H2000b20006008,212,6868,224,34211,437,590
H2000c20006005,564,2396,146,6256,165,039
H2000d200060019,542,85321,978,22221,355,459
H100010003001,307,2071,618,1791,393,363
C32783011,49911,49911,499
C2260307,3487,3487,348
C2142306,9446,9446,944

Q3. Please provide a formal definition of "RTDL" upon its first mention.

RTDL is a shorthand for Representation Topology Divergence Lite, RTD-Lite (Tulchinskii et al., 2025). We are adding a remark in Introduction, Section 3.

Q4. On MST computation time.

The MST (and RTDL) computation is always included in wall-clock runtimes. Appendix Z states the RTDL cost and compute setup. We are adding a remark on it in Appendix Z.

Q5. On comparison with Concorde in Table 5.

Table 5 reports gaps relative to Concorde's best solution for each TSPLIB instance, so Concorde is already the reference optimum. This is explained in the table’s caption. We are making the reference explicit in the Table 5 header.


Concluding remarks. We hope these additional experiments address the Reviewer's concerns regarding NeuroLKH. We welcome any further questions and would appreciate reconsideration of the overall rating in light of the new evidence.

Thank you for the detailed responses. I would like to raise my score to 2, while my concern still remains regarding the contribution to the ICLR community.

We thank the Reviewer for the constructive discussion and for raising the score. Regarding the remaining concern on contribution to the ICLR community, we would like to respectfully highlight that the paper's central results concern learning-based solvers, and the proposed signal is a general mechanism for improving them at test time:

  1. Training-free test-time improvement of neural solvers. RTDL acts as an external topological prior that guides the search of pretrained, unmodified models - analogous to guidance in decoding for generative models, but for combinatorial search. We demonstrate this across six learned frameworks without any retraining or calibration data:
  • heatmap solvers (DIFUSCO, SoftDist, DIMES, UTSP, ATT-GCN): shorter tours everywhere (p<10−8p < 10^{-8}) and up to ~14× post-processing speedup at n=104n=10^4 (112.73h → 7.99.0h, Table 4);
  • L2C, the current SOTA learned constructive solver: a one-line change to its inference loop reduces the optimality gap by 0.47–0.56pp (Table 3);
  • New experimental results with FastT2T: post-processing with a topological signal applied to tours via Fast-T2T is better in both length and wall-clock time, see Response to VGWK;
  • INViT: statistically significant gap reduction via gap-based edge banning (Table 10).
  1. A contribution to RL. The potential-based reward shaping r=−w(e)−λ⋅p(e)r = −w(e) − \lambda·p(e) provably preserves the optimal policy and stabilizes DQN training, which otherwise diverges (TSP-100: 18.66 → 11.75, Appendix J). This is a reusable recipe for shaping CO-RL rewards with topological signals.

  2. A conceptual bridge. The paper shows that persistent-homology tools (RTD-Lite barcodes) yield an actionable, per-edge signal for neural CO - with guarantees (zero-penalty law, α\alpha-nearness as a degenerate bar, lower bound) that explain why it composes with learned priors. Additional experiments with NeuroLKH were conducted, see Response to VGWK. We note the complementarity that our NeuroLKH comparison demonstrates: learned, instance-independent candidate models degrade on hard topologies, while the tour-dependent topological signal requires no training data - addressing exactly the "real-world implementation" property the reviewer lists among the paper's critical strengths.

We believe this positions the work within ICLR's scope of learning-based optimization and test-time methods, beyond a classical CO improvement. We are grateful for the Reviewer's time, and would happily provide further evidence if any aspect remains unclear.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Overall Author Response Summary, Request for Reviewer Reassessment

Dear Area Chair,

We thank the reviewers for their constructive feedback. We have now provided detailed, point-by-point responses to all concerns raised across the three reviews, including substantial new experiments, stronger baseline comparisons, and clarifications of the theoretical contributions and empirical claims.

We would particularly like to highlight the following developments:

  1. Stronger baselines (T2NN, VGWK): We added matched-budget comparisons with NeuroLKH and Fast-T2T, directly addressing the reviewers' requests. LKH+RTDL achieves shorter tours than both NeuroLKH variants on all nine evaluated hard instances (n=1000n=1000–5000). For Fast-T2T at n=10000n=10000, our method improves tour length from 74.58 to 73.44, while reducing post-processing time from 25.71h to 3.28h (approximately 7.8× faster). These results substantially strengthen the evidence beyond the original baselines.

  2. Practical efficiency (T2NN, VGWK): We clarified that reported wall-clock times include MST and RTDL computation. Furthermore, LKH+RTDL achieves a 21.4% average CPU reduction, with faster execution in all 180 matched runs across nine hard instances, while preserving tour quality.

  3. Theoretical contribution (VGWK): We clarified the relationship to RTD-Lite, explicitly distinguishing its general barcode machinery from our TSP-specific tour-dependent edge penalties, their structural interpretation, and their integration into optimization algorithms. We also provided additional discussion of the theoretical guarantees and their relationship to established edge-scoring methods.

  4. Ablations and presentation (sbb5): We added a direct L2C comparison against long-edge prioritization, which shows no statistically significant improvement, unlike RTDL-guided selection. We also acknowledged and addressed the reported numerical inconsistencies, clarified statistical significance, and narrowed the ATSP/HCP claims to their experimentally supported scope.

Importantly, these results reinforce the paper's relevance to ICLR: a training-free, theoretically motivated structural signal that improves both classical optimization and the inference-time performance of pretrained neural TSP solvers without retraining.

We have responded to every concern raised in the three reviews. To date, we have not received follow-up responses or additional questions from the reviewers. We would therefore be very grateful if the Area Chair could encourage the reviewers to examine the rebuttals and new evidence, indicate whether any substantive concerns remain, and reconsider their scores and recommendations accordingly.

We believe the additional experiments and clarifications materially strengthen the submission and its case for acceptance. We sincerely appreciate your consideration and the reviewers' time.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.