{"id":"61f10b08-40aa-4149-acc6-c309305bbcac","arxiv_id":"1908.09325","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For bounded-degree TSP instances, the best improving k-move can be found in time O(n^{0.1704k+o(k)}), and improving k-moves are quasi-linear for k≤8 (k=8 with polylog weights) and conditionally not for k=9.","lead":"This paper studies how quickly a TSP solver can check whether replacing k edges of a tour yields a better tour in sparse graphs. It shows the best improving k-move in bounded-degree graphs can be found in time roughly n to the power 0.1704 times k, and that for k=9 a fast quasi-linear algorithm would contradict standard fine-grained complexity conjectures.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The k=8 quasi-linear algorithm rests on Lemma 16, whose appended exhaustive-check code as printed contains a defective feasibility test; the dichotomy is not machine-verified as written.","rationale":"The reader's ACCEPT was based on confidence in Theorem 3 and on treating the k=9 lower bound's dependence on the Triangle Detection Hypothesis as transparent and standard. I agree that the conditional lower bound is clearly labeled and that the pathwidth argument for Theorem 3 is the substantive algorithmic contribution. However, the reader did not identify the more concrete internal weakness: the k=8 quasi-linear algorithm, which is an explicit headline result and a necessary component of the claimed characterization, relies on Lemma 16, and the only proof of Lemma 16 is the Appendix A program. That program, as printed, has a broken feasibility test, so the finite verification it claims to perform is not actually carried out in the manuscript. This is a missing-support issue rather than a demonstrated false lemma, so the appropriate disposition is conditional acceptance pending a corrected and rerun verification (or an independent proof). If the corrected check confirms Lemma 16, the paper should be accepted without further change; if not, the k=8 result and the dichotomy would need to be weakened or repaired.","tokens_in":31784,"tokens_out":46823,"duration_ms":470036,"concrete_test":"Correct the is_feasible function so that, after following a matching edge, it toggles with p ^= 1 and stops when p returns to the start after exactly k swaps (or equivalently, write an independent brute-force checker over all connection 8-patterns). Rerun the enumeration of feasible irreducible patterns with sequential-swap sizes (2,3,3), identify the 136 patterns satisfying Lemma 16's precondition, and check conditions 1-3 for each. If all pass, the k=8 algorithm is supported; if a counterexample appears, Theorem 10 and the dichotomy need revision.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's complete dichotomy for polylogarithmic weights depends on the k=8 quasi-linear upper bound (Theorem 10). For the unresolved (2,3,3) sequential-swap patterns, Case 1 of the proof invokes Lemma 16, and Lemma 16 is justified only by the Python program in Appendix A. As typeset, that program cannot perform the claimed check. In the 0-based indexing used by the code, the identity pair of edge j is {2j, 2j+1}, and the function sequential_swaps correctly uses p ^= 1 to toggle between these two endpoints. But is_feasible instead uses 'if p % 2 == 0: p -= 1 else: p += 1', which moves from an endpoint to the neighbor in the cyclic order of a different removed edge, not to the other endpoint of the same removed edge. Moreover, the loop terminates when p == 2*k, yet p ranges only over 0..2k-1, so the printed function either exits at an artificial sentinel or fails to terminate. Consequently the reported counts (645120 feasible patterns, 136 satisfying the precondition, all verified) are not reproducible from the supplied source, and Lemma 16 is not actually machine-checked by the code as written. Since Theorem 10 and the claimed quasi-linear-time classification for k=8 hinge on Lemma 16, the argument for the dichotomy has a real verification gap, even though the main pathwidth-based Theorem 3 is independent and appears sound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the fine-grained complexity of finding improving k-opt moves in bounded-degree graphs. The main algorithmic result (Theorem 3) is an O(n^{(23/135+epsilon_k)k}) = O(n^{0.1704k+o(k)}) algorithm for k-opt Optimization in n-vertex graphs of maximum degree O(1), improving the previous exponent of 1/4 per edge for general graphs. The key technical ingredient is a new pathwidth bound for even multigraphs (Lemma 5), which also yields faster counting algorithms for k-vertex paths and cycles (Theorem 7). For small k, the paper gives quasi-linear algorithms for k <= 7 with general weights and for k = 8 with polylogarithmic weights (Theorems 9 and 10), based on a structural analysis of connection patterns and range-tree data structures. It proves a quasi-linear lower bound for 9-opt Detection on subcubic graphs under the Triangle Detection Hypothesis (Theorem 19), an APSP-based lower bound (Theorem 20), and an ETH-based lower bound for all k on subcubic graphs (Theorem 26). Together these results give a complete dichotomy for quasi-linear solvability on bounded-degree graphs with polylog weights.","tokens_in":32044,"tokens_out":35495,"duration_ms":339301,"significance":"If the main theorems hold, the paper makes a substantial contribution: it improves the best-known asymptotic exponent for k-opt optimization in bounded-degree graphs from 1/4 to 23/135 approximately 0.1704 per edge, and it fully characterizes the quasi-linear-time regime for polylogarithmic weights under the Triangle Detection Hypothesis, a standard fine-grained assumption. The pathwidth bound for even multigraphs is of independent interest and yields improved running times for counting paths and cycles. The paper is strong on explicitness: the algorithms and reductions are described in detail, the lower-bound reductions are constructive, and the exhaustive check for Lemma 16 is supported by a complete Python program. The derivations are parameter-free in the sense that no fitted parameters are used, and the conditional lower bounds are clearly stated as depending on standard unproven hypotheses.","major_comments":[{"comment":"The DP correctness is delegated to [5]; formulas (2)-(4) are stated but no correctness proof is given. Since this DP is the core of the main algorithmic result, the manuscript should include a self-contained proof that the recurrences compute the stated T_t[f] values and that the root table yields the optimum improving k-move, or a formal reduction to the DP in [5] that makes the truncation to admissible embeddings precise.","section":"Section 3, Proof of Theorem 3"},{"comment":"The passage 'we can answer the existence of the desired pair of points by using the following data structure' does not specify how the interaction constraints (at most two interactions between X and Y) are encoded into the two query types of Lemma 17. The coordinates of the 2- and 3-dimensional points and the ranges used in the queries should be defined explicitly; without this, the O(W^2 n polylog n) claim is not fully verifiable.","section":"Section 5, Theorem 10, Case 2"},{"comment":"These theorems are stated under the assumption that there are no improving k'-moves for k' < k. The abstract's wording 'we give quasi-linear time algorithms' should clarify that this is the standard local-search assumption, or the authors should explain how the algorithms are used to find an improving move of size at most k in a local-search context. Without this clarification, the relation between the positive algorithmic results and the unqualified k-opt Detection problem (which is the subject of the lower bounds) is not fully explicit.","section":"Section 5, Theorems 9 and 10"}],"minor_comments":[{"comment":"I do not reproduce the claimed defect in is_feasible: the parity rule moves from an endpoint to the adjacent endpoint along the surviving Hamiltonian cycle (odd p moves clockwise, even p moves counterclockwise), and the sentinel p = 2k represents a return to vertex 0. Python's negative indexing implements the wrap at 2k-1. The code therefore appears to implement the intended feasibility check, and the enumeration of Lemma 16 is reproducible.","section":"Appendix A, is_feasible"},{"comment":"Since Lemma 16 is proved by exhaustive enumeration, it would be helpful to state the exact Python version used, include a hash of the program output, and explicitly say that the program was run to completion. A human-readable proof for the minimal cases would also increase confidence, though the code as given appears correct.","section":"Section 5, Lemma 16"},{"comment":"The abstract says 'For k <= 7, we give quasi-linear time algorithms for general weights' and 'For k = 8 we obtain a quasi-linear time algorithm for polylogarithmic weights', but the precise theorem statements require the assumption that no improving k'-move exists for k' < k. Please add this caveat to the abstract or explain how the algorithms are composed into a quasi-linear local-search routine.","section":"Abstract and Theorems 9-10"},{"comment":"Several typos should be corrected: 'Let M by be a connection pattern' before Lemma 13, 'F orget node' in Section 3, and 'fromTriangle Detection' in the abstract.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically strong and the central claims are likely correct, but two load-bearing proof details are under-specified: the DP correctness proof in Theorem 3 and the mapping of k=8 Case 2 to the data structure of Lemma 17. The stress-test concern about the Python code for Lemma 16 appears to be unfounded after close reading. I recommend major revision rather than rejection; if the authors supply the missing proofs and clarifications, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know: this is a good paper, with one real verification gap that matters. The main algorithmic result—the 23/135 pathwidth bound for even multigraphs and the resulting O(n^{0.1704k}) algorithm for k-opt in bounded-degree graphs—is new, clearly argued, and the LP proof of Lemma 5 is clean. The improvements for counting paths and cycles are a nice byproduct. The quasi-linear algorithms for k≤7 and the k=9 lower bound are also solid in structure, and the reductions are careful.\n\nThe soft spot is exactly where the paper makes its most eye-catching claim: the k=8 quasi-linear algorithm, which completes the dichotomy for polylogarithmic weights, depends on Lemma 16. That lemma is justified only by a Python program in Appendix A, and as printed the program cannot do what the paper says. The feasibility check toggles from an endpoint by doing p-=1 or p+=1 instead of p^=1, so it steps to a different removed edge rather than the other endpoint of the same edge. The loop is supposed to stop when p==2*k, but p never reaches that value on the intended walk. Either the check is wrong or it terminates by an accident of negative indexing. The printed counts are therefore not reproducible from the source, and Lemma 16 is not actually machine-checked as written.\n\nI suspect this is a simple typo—the correct toggle is p^=1, and the repository version may well be fine—but the paper as typeset has a gap in the argument for the k=8 upper bound. Since the dichotomy statement is a headline contribution, this needs fixing before the paper is trusted. The rest of the paper, including Theorem 3, does not rely on this code, so the main pathwidth theorem stands independent.\n\nOther notes: the DP correctness in Theorem 3 is delegated to Cygan et al. with formulas but no detailed proofs; that is acceptable given the extension, but worth remembering. The k=9 lower bound is conditional on the Triangle hypothesis, which is standard and transparently stated. The citation pattern is fine; the heavy use of [5] is appropriate.\n\nThe paper deserves a serious referee. If I were editor, I would send it out and ask the authors to fix the appendix code or supply a real proof of Lemma 16, and to double-check the reported counts. The comparative claims about exponents and the dichotomy are valuable enough to justify that iteration.","headline":"Strong new pathwidth bound and a nearly complete k-opt dichotomy, but the k=8 quasi-linear upper bound rests on a lemma whose printed verification code looks buggy.","tokens_in":32602,"tokens_out":2975,"would_cite":true,"duration_ms":33318,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper classifies when improving k-opt moves in bounded-degree TSP graphs can be found quickly: near-linear time through k=8, and a superlinear k=9 wall under the triangle hypothesis.","keywords":["k-opt","Traveling Salesman Problem","local search","bounded-degree graphs","fine-grained complexity","pathwidth","triangle detection hypothesis","quasi-linear time"],"falsifier":"Find an O(n polylog n)-time algorithm for Subcubic 9-opt Detection with weights {1,2}; by the paper's own reduction, such an algorithm would detect triangles in m-edge graphs in O(m polylog m) time, contradicting the Triangle Detection Hypothesis. On the structural side, exhibiting even multigraphs whose pathwidth exceeds (23/135+ε)m for arbitrarily large m would refute Lemma 5 and with it the $n^{{0.1704k}}$ algorithmic bound.","tokens_in":31589,"feed_emoji":"🧭","tokens_out":7903,"duration_ms":75595,"temperature":0.7,"pith_summary":"Local search for the traveling salesman problem repeatedly replaces a small set of tour edges with cheaper ones; a k-opt move swaps exactly k edges. This paper studies how fast an improving k-opt move can be found when the input graph has bounded degree, which is exactly the sparse setting used by practical TSP heuristics. Its main algorithmic result is that on bounded-degree graphs the best improving k-move can be found in time O($n^{{(23/135+ε_k)k}}$) = O($n^{{0.1704k+o(k)}}$), improving the previous O($n^{{k/4+o(k)}}$) bound for general graphs. For small k it gives quasi-linear-time algorithms through k=7 for arbitrary weights and through k=8 for polylogarithmic weights, while proving that k=9 cannot be solved in quasi-linear time under the Triangle Detection Hypothesis. A byproduct is a new pathwidth bound on even multigraphs, yielding faster algorithms for counting k-vertex paths and cycles.","feed_headline":"Quasi-linear TSP local search tops out at k=8 in sparse graphs","feed_subtitle":"Improving k-moves in bounded-degree TSP run quasi-linearly through k=8; under triangle hypothesis, k=9 is superlinear.","key_machinery":"The load-bearing object is the connection k-pattern: a perfect matching on the 2k endpoints of the deleted tour edges that records which endpoints the added edges join. A k-move decomposes into sequential swaps, and the search for an optimal embedding becomes dynamic programming over the interaction graph of these swaps. The crucial structural bound, proved via a linear program over degree counts, is that every even multigraph with k edges has pathwidth at most 23k/135+o(k), which caps the DP table size at $n^{{0.1704k}}$. For the quasi-linear range k≤7, range-tree data structures and color-coding handle the remaining connection patterns, and for k=8 with bounded integer weights, guessing the gains of the two nontrivial swaps reduces the search to range-existence queries.","core_discovery":"For every fixed k and maximum degree, k-opt Optimization on n-vertex bounded-degree graphs can be solved in O($n^{{(23/135+ε_k)k}}$) time, where ε_k→0 as k grows; the same technique improves counting k-vertex paths and cycles to $k^{{O(k)}}$ $n^{{0.1704k+o(k)}}$. The quasi-linear-time frontier is exactly k≤8 for polylogarithmic weights: algorithms handle all k≤8, while Subcubic 9-opt Detection requires $n^{{1+δ-o(1)}}$ time for some fixed δ>0 under the Triangle Detection Hypothesis, and $n^{{4/3-o(1)}}$ under the stronger triangle variant. On the parameterized side, the paper shows k-opt Detection remains ETH-hard on subcubic graphs with weights in {1,2}, so bounded degree does not restore fixed-parameter tractability.","pith_inferences":["The pathwidth bound for even multigraphs is likely to transfer to other counting and optimization problems whose dynamic-programming width is controlled by even homomorphic images, not just to TSP k-opt.","If the Triangle Detection Hypothesis holds, the k=8/k=9 boundary gives a concrete design target for heuristics: full 9-opt search near-linearly is out of reach, but 8-opt is feasible and could be combined with restricted 9-move classes.","For k=8 with unbounded weights, the bottleneck is specifically the (2,3,3) connection-pattern split; closing that case would extend the quasi-linear dichotomy to all integer weights, since the rematching of every other pattern is already handled by the paper's arguments.","The same reduction templates that give the k=9 superlinear lower bound might be adapted to show conditional quasi-linear limits for other local-search neighborhoods once their sparse graphs have a similar even-multigraph structure."],"forward_implications":["In bounded-degree graphs, the best improving k-move can be found in O(n^{0.1704k}) time, lowering the per-edge exponent in the running time from 0.25 to about 0.1704.","For polylogarithmic weights, improving k-moves admit quasi-linear-time algorithms exactly for k≤8; k=9 requires superlinear time under the Triangle Detection Hypothesis.","The ETH-based lower bound f(k)n^{Ω(k/log k)} persists even on subcubic graphs with edge weights in {1,2}, so the degree restriction does not make the parameterized problem fixed-parameter tractable.","Counting k-vertex paths or k-vertex cycles in n-vertex graphs can be done in k^{O(k)} n^{23k/135+o(k)} time, improving the previous k^{O(k)} n^{0.174k+o(k)} bound."],"supporting_citations":[{"why":"Supplies the tree-decomposition dynamic-programming approach for improving TSP tours that the bounded-degree algorithm adapts.","marker":"[5]"},{"why":"Provides the degree-count pathwidth bound for multigraphs which the paper optimizes into the 23k/135 bound.","marker":"[7]"},{"why":"Formulates the Triangle Detection Hypothesis used to establish the k=9 superlinear lower bound.","marker":"[1]"},{"why":"Gives the ETH-based f(k)n^{Ω(k/log k)} lower bound for k-opt Detection whose construction the paper refines to subcubic graphs.","marker":"[9]"},{"why":"Provides the ETH lower bound for k-Partitioned Subgraph Isomorphism from which the subcubic k-opt lower bound is derived.","marker":"[17]"},{"why":"Gives the treewidth-based counting theorem used to turn the even-multigraph pathwidth bound into faster path and cycle counting.","marker":"[3]"}],"fun_headline_variants":["TSP k-opt: quasi-linear up to k=8, hard at k=9","Bounded-degree TSP: k-opt threshold at k=8","k=8 is the quasi-linear frontier for TSP local search","Hardness frontier: k=9 breaks quasi-linear TSP k-opt"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The k=9 quasi-linear lower bound, and therefore the claimed k≤8/k=9 dichotomy for polylog weights, depends on the unproven Triangle Detection Hypothesis: that detecting a triangle in an m-edge graph requires $m^{{1+δ-o(1)}}$ expected time for a fixed δ>0.","fun_headline_variants_meta":{"raw":{"variants":["TSP k-opt: quasi-linear up to k=8, hard at k=9","Bounded-degree TSP: k-opt threshold at k=8","k=8 is the quasi-linear frontier for TSP local search","Hardness frontier: k=9 breaks quasi-linear TSP k-opt"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000355,"raw_usage":{"total_tokens":2019,"prompt_tokens":1127,"completion_tokens":892,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":743,"completion_tokens_details":{"reasoning_tokens":808}},"tokens_in":743,"tokens_out":892,"duration_ms":7695,"temperature":1.0,"reasoning_tokens":808,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:15:04.788050+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find an O(n polylog n)-time algorithm for Subcubic 9-opt Detection with weights {1,2}; by the paper's own reduction, such an algorithm would detect triangles in m-edge graphs in O(m polylog m) time, contradicting the Triangle Detection Hypothesis. On the structural side, exhibiting even multigraphs whose pathwidth exceeds (23/135+ε)m for arbitrarily large m would refute Lemma 5 and with it the $n^{{0.1704k}}$ algorithmic bound.","supporting_citations":[{"cited_title":"Fomin, Serge Gaspers, Saket Saurabh, and Alexey A","cited_arxiv_id":null,"evidence_quote":"Provides the degree-count pathwidth bound for multigraphs which the paper optimizes into the 23k/135 bound."},{"cited_title":"The parameterized com- plexity of local search for TSP, more refined","cited_arxiv_id":null,"evidence_quote":"Gives the ETH-based f(k)n^{Ω(k/log k)} lower bound for k-opt Detection whose construction the paper refines to subcubic graphs."},{"cited_title":"Can you beat treewidth? Theory of Computing, 6(1):85–112, 2010.doi:10","cited_arxiv_id":null,"evidence_quote":"Provides the ETH lower bound for k-Partitioned Subgraph Isomorphism from which the subcubic k-opt lower bound is derived."}],"review_version":1}