reproduce the original tour. Three pieces can be patched together to form a different tour in one way only, and the corresponding alternating trail does not extend to a closed trail for rearranging four pieces into a new tour. To rearrange four pieces, one needs a non-sequential exchange. Checking Hamiltonicity The Lin–Kernighan heuristic checks the validity of tour candidates at two points: obviously when deciding whether a better tour has been found, but also as a constraint to descending in the search tree, as controlled via the infeasibility depth . Concretely, at larger depths in the search a vertex is only appended to the alternating trail if is a tour. By design that set of edges constitutes a 2-factor in , so what needs to be determined is whether that 2-factor consists of a single Hamiltonian cycle, or instead is made up of several cycles. If naively posing this subproblem as giving a subroutine the set of edges as input, one ends up with as the time complexity for this check, since it is necessary to walk around the full tour before being able to determine that it is in fact a Hamiltonian cycle. That is too slow for the second usage of this test, which gets carried out for every alternating trail with more than edges from . If keeping track of more information, the test can instead be carried out in constant time. A useful degree of freedom here is that one may choose the order in which step 2.3.2 iterates over all vertices; in particular, one may follow the known tour . Note that after picking edges from , the remaining subgraph consists of paths. The outcome of the Hamiltonicity test done when considering the th edge depends only on in which of these paths that resides and whether is before or after . Hence it would be sufficient to examine different cases as part of performing step 2.3.2 for ; as far as is concerned, the outcome of this test can be inherited information rather than something that has to be computed fresh. References External links LKH implementation Concorde TSP implementation LK Heuristic in Python Combinatorial optimization Combinatorial algorithms Heuristic algorithms Travelling salesman problem