PaperlayerView exact revision on arXiv

Source-linked AI summary

Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment

Sophia Heimann, Hung P. Hoang, Stefan Hougardy

arXiv:2610.31513v1cs.DSmath.CO

TL;DR

The paper addresses whether 2-opt TSP and small-parameter binary MCA problems can force exponential local-search runs under every pivot rule. It gives direct recursive constructions and proves the all-exp property for 2-opt TSP and for (3, 2, 2)- and (2, 3, 2)-MCA, with the MCA bounds tight under parameter decreases.

  • Problem

    Whether every pivot rule can be forced to take exponentially many iterations remained open for 2-opt TSP and several small-parameter MCA cases.

    Source: §1 · pp. 2–4

  • Method

    The proofs use direct recursive constructions that enforce dependencies between layers; the 2-opt construction uses tour-feasibility restrictions, while MCA uses gadgets to preserve the dependencies.

    Source: §1 · p. 5

  • Results

    The 2-opt TSP and (3, 2, 2)- and (2, 3, 2)-MCA with flips have the all-exp property.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The results complete the all-exp classification of k-opt TSP neighborhoods and show that decreasing any parameter of either stated MCA case yields polynomial-length improving flip sequences.

    Source: §1 · pp. 3–4

Abstract

from arXiv · show

We prove the all-exp property for the Traveling Salesman Problem with the $2$-opt neighborhood, and for $(3,2,2)$- and $(2,3,2)$-Maximum Constraint Assignment with the flip neighborhood. The all-exp property states that infinitely many instances have an initial solution from which every sequence of improving moves to a local optimum, and hence every run of local search, has exponential length. For the Traveling Salesman Problem, the all-exp property was previously known for every $k$-opt neighborhood with $k \ge 3$, so our result for $2$-opt completes the picture for all $k$-kopt neighborhoods. In $(p,q,r)$-Maximum Constraint Assignment, each constraint involves at most $p$ variables, each variable occurs in at most $q$ constraints, and each domain has size $r$. Decreasing any of the parameters of $(3,2,2)$ or $(2,3,2)$ yields a problem in which every sequence of improving flips has polynomial length, so both Maximum Constraint Assignment results are tight. All three results settle long-standing open problems. Our proofs build on a common construction idea, which reveals a close connection between the local-search dynamics of the three problems.

1 Introduction

The paper resolves the remaining all-exp questions for 2-opt TSP and two tightly bounded binary MCA problems. Its direct recursive constructions show how every improving path can be forced to have exponential length.

1 Introduction

  • For TSP, this settles the last open k-opt neighborhood, since the all-exp property was already known for every k ≥3.The paper also states that 2-opt is the smallest k-opt neighborhood.Source: §1 · p. 3
  • The 2-opt TSP, (3, 2, 2)-MCA, and (2, 3, 2)-MCA with flips all have the all-exp property.For each, infinitely many initial solutions force every improving sequence to a local optimum to be exponentially long.Source: §1 · pp. 2–4
  • Decreasing any parameter of (3, 2, 2)- or (2, 3, 2)-MCA yields polynomial-length improving flip sequences, making both results tight.Only (2, 2, 3)- and (2, 2, 4)-MCA remain open among the cases discussed.Source: §1 · p. 4
  • The proofs use a shared layered recursion: traversing one layer requires at least two traversals of the preceding layer, forcing exponential sequence length.The construction must prevent improving moves from bypassing these dependencies.Source: §1 · pp. 4–5
  • For 2-opt, feasibility restrictions exclude otherwise improving shortcuts, while all maximal sequences differ only in the order of a few independent moves.The construction is direct rather than a reduction from Max-Cut; previous k ≥3 constructions could exclude unwanted moves through edge weights alone [HHH26b].Source: §1 · pp. 3, 5
  • For (2, 3, 2)-MCA, bounded-occurrence gadgets preserve recursive dependencies, and a directed acyclic graph captures simultaneous flips so all maximal sequences have equal exponential length.The construction adapts the recursive approach of Michel and Scott while limiting each variable to at most three constraints.Source: §1 · p. 5

2 Preliminaries

The preliminaries define local-search problems and the all-exp property, then specify the TSP swap neighborhood and binary MCA flip model used in the paper.

2.1 Local-search problems

  • A local-search problem specifies instances, feasible solutions, an objective, and a neighborhood; a local optimum has no better neighbor.An improving move has positive gain, and a maximal improving sequence ends at a local optimum.Source: §2.1 · p. 6
  • The all-exp property requires infinitely many instance–initial-solution pairs for which every pivot rule takes exponentially many iterations to reach a local optimum.Equivalently, every path from the initial solution to a sink in the transition graph is exponentially long.Source: §2.1 · p. 6

2.2 TSP with the k-opt neighborhood

  • In TSP k-opt, a neighbor tour results from swapping at most k edges for the same number of edges, with improving swaps reducing tour weight.A sequence of such swaps corresponds to an execution of the k-opt local-search algorithm.Source: §2.2 · p. 7

2.3 Maximum Constraint Assignment

  • In (p, q, r)-MCA, constraints involve at most p variables, each variable occurs in at most q constraints, and each variable has a domain of size r.The paper focuses on binary domains; a flip changes one variable's value, and an improving flip increases the assignment value.Source: §2.3 · p. 7

3 (3,2,2)-MCA has the all-exp property

The (3,2,2)-MCA flip neighborhood has the all-exp property. A direct layered construction forces a unique exponentially long improving sequence from the all-zero assignment, ending at a local optimum.

3 (3,2,2)-MCA has the all-exp property

  • (3,2,2)-MCA with the flip neighborhood has the all-exp property.The construction has 6n+2 variables and 4n+1 constraints, with weights encoded using O(n^2) bits.Source: §3 · pp. 7–8, The construction · p. 12

The construction.

  • The instances use n+1 layers, with two base variables and six variables per later layer, and are 3-partite.Each later layer has four constraints; all variables are binary.Source: The construction · p. 8
  • Each layer recursively runs the preceding layer's sequence twice, interleaved with six flips in the new layer.The recursion is S_i = (v_i,1, S_{i−1}, v_i,2, v_i,3, S_{i−1}, v_i,4, v_i,5, v_i,6).Source: The construction · pp. 9, 12
  • From the all-zero assignment, the construction has a unique maximal improving sequence of exponential length.The number of flips is 8 · 2n −6 as printed in the passage.Source: The construction · pp. 9, 12
  • At every step exactly one variable is improving, each flip gains exactly one, and the sequence ends at a local optimum.The recursive construction forces both occurrences of the preceding sequence to complete before the next layer flip.Source: The construction · pp. 10–12

4 TSP with the 2-opt neighborhood has the all-exp property

This section proves that TSP with the 2-opt neighborhood has the all-exp property, using a construction that yields exponentially long improving sequences from a prescribed initial tour on instances of polynomial encoding size. It also characterizes every maximal improving sequence from that initial solution.

4 TSP with the 2-opt neighborhood has the all-exp property

  • For every n, an O(n)-vertex instance has an initial tour from which every maximal improving 2-opt sequence lasts Ω(2^n) moves and reaches the same local optimum.These sequences are identical up to interchanging certain commuting swaps; the theorem concludes that TSP with 2-opt has the all-exp property.Source: §4 · p. 12, §4.4 · p. 20

4.1 The construction

  • The construction chains n+1 gadget layers through identified interfaces to form a Hamiltonian initial tour, and prohibitively heavy completion edges cannot enter an improving 2-opt sequence.The constructed graph is completed to a TSP instance by adding missing edges with very large weights, without changing the improving sequences from the initial tour.Source: §4.1 · pp. 13–14

4.2 Tour characterization

  • The layer-path invariant characterizes tours: boundary layers contain spanning paths, while each interior layer contains two spanning paths connecting distinct pairs of its four interfaces.A 2-regular subgraph satisfying this invariant is a Hamiltonian cycle.Source: §4.2 · p. 15

4.3 States of the tour

  • Interface and gadget states encode reachable tours, and every 2-opt swap changes exactly one state; conversely, single-state changes are swaps except for two Ei state pairs.The exceptions are the Ei pairs {0, 3} and {1, 4}, whose changes exchange three edges rather than two.Source: §4.3 · pp. 16–18

4.4 Correctness

  • The canonical improving sequence governs every run: after deleting E4i changes, the ordinary moves form its prefix, while E4i moves may be reordered within specified intervals.At each reachable tour, the only improving changes are the next applicable ordinary change and eligible E4i changes.Source: §4.4 · p. 20
  • Every improving sequence from τ0 is a prefix of a rearrangement of Pn, with choices limited to the next ordinary change or an available E4_i change.The induction shows that the available improving changes at each prefix preserve the required order; maximal sequences differ by moving E4_i between D0_i and E0_i.Source: §4.4 · p. 23
  • For n ≥ 2, every maximal improving swap sequence from τ0 has length 9 · 2^(n−1) − 7; for n = 1, each has length 3.The canonical sequence Pn is maximal, and all maximal sequences arise by moving E4_i occurrences between their corresponding D0_i and E0_i.Source: §4.4 · p. 23
  • TSP with 2-opt has the all-exp property: the instances have O(n) vertices and weights encoded in O(n) bits, while every maximal sequence has exponential length.For n ≥ 2, the length is 9 · 2^(n−1) − 7.Source: §4.4 · p. 23

5 (2,3,2)-MCA has the all-exp property

This section establishes the all-exp property for (2,3,2)-MCA under the flip neighborhood. Its construction yields exponentially long improving sequences.

5 (2,3,2)-MCA has the all-exp property

  • Theorem 3 establishes the all-exp property for (2,3,2)-MCA with the flip neighborhood.Source: §5 · p. 23

5.3 The construction

  • The construction replaces two degree-four interfaces with degree-three gadgets: one computes a three-input XOR, while a copy chain propagates flips at the other.Source: §5 · p. 23, §5.3 · pp. 26, 28

5.1 Graph representation of binary MCA

  • A weighted graph of maximum degree q represents a (2,q,2)-MCA instance, so constructing a graph of degree at most three suffices here.Source: §5.1 · p. 24

5.2 The “following” primitive

  • The following primitive gives a vertex a unique locally preferred value determined by a Boolean function of its neighbors, making a mismatching flip improving.Source: §5.2 · p. 24

5.4 Correctness

  • Every maximal improving flip sequence is a rearrangement of the canonical sequence, whose length satisfies T0 = 2 and Tn = 3Tn-1 + 35.This recurrence gives exponentially growing sequence lengths.Source: §5.4 · pp. 28, 30
  • The acyclic dependency graph D_n has unique source 1, every vertex reaches T_n, and its linear extensions correspond bijectively to maximal improving sequences labeled by Ω_n.Source: §5.4 · pp. 31, 33, 34
  • Under Lemma 24’s stated conditions, maximal sequences on layers F_0,…,F_m are exactly the D_m linear extensions labeled by Ξ_m^ε, and the layers switch to phase 1−ε.The phase-switch property follows from matching flip parity of Ω_m and its complementary string.Source: §5.4 · pp. 30, 32
  • Every maximal improving sequence from σ0 has length T_n and ends at the same local optimum, with every layer in phase 1 and v′0 = v′1 = v′2 = 0.The construction establishes that T_n is exponential in n.Source: §5.4 · p. 34
  • The construction proves the all-exp property for (2,3,2)-MCA with flips, using O(n) variables and maximal improving sequences of length Θ(3^n).The constructed graph has maximum degree three, and each weight can be encoded with O(n) bits.Source: §5.4 · p. 34

AI methodology

The authors report that AI tools did not produce the paper’s main results or proofs. ChatGPT 5.6 Sol and Claude Fable 5.1 were used to generate code that optimized construction weights and sizes.

AI methodology

  • The authors obtained all three main results without using AI tools.They state that the authors carried out all proofs and take full responsibility for their correctness.Source: AI methodology · p. 34
  • ChatGPT 5.6 Sol and Claude Fable 5.1 generated Python code to optimize construction weights and sizes.This produced slightly simpler constructions but did not affect the results’ statements.Source: AI methodology · p. 34
  • The authors carried out all proofs and take full responsibility for their correctness.Source: AI methodology · p. 34
Loading 2610.31513v1…