trail multiple times, with different starting points, but Lin–Kernighan does not care because it mostly aborts the enumeration after finding the first hit. It should however be remarked that: Lin–Kernighan is not satisfied with just having found a closed alternating trail of positive gain, it additionally requires that is a tour. Lin–Kernighan also restricts the search in various ways, most obviously regarding the search depth (but not only in that way). The above unrestricted search still terminates because at there is no longer any unpicked edge remaining in , but that is far beyond what is practical to explore. In most iterations one wishes to quickly find a better tour , so rather than actually listing all siblings in the search tree before exploring the first of them, one may wish to generate these siblings lazily. Basic Lin–Kernighan algorithm The basic form of the Lin–Kernighan algorithm not only does a local search counterpart of the above enumeration, but it also introduces two parameters that narrow the search. The backtracking depth is an upper bound on the length of the alternating trail after backtracking; beyond this depth, the algorithm explores at most one way of extending the alternating trail. Standard value is that . The infeasibility depth is an alternating path length beyond which it begins to be required that closing the current trail (regardless of the gain of doing so) yields an exchange to a new tour. Standard value is that . Because there are alternating trails of length , and the final round of the algorithm may have to check all of them before concluding that the current tour is locally optimal, we get (standard value ) as a lower bound on the exponent of the algorithm complexity. Lin & Kernighan report as an empirical exponent of in the average overall running time for their algorithm, but other implementors have had trouble reproducing that result. It appears unlikely that the worst-case running time is polynomial. In terms of a stack as above, the algorithm is: Input: an instance of the travelling salesman problem, and a tour Output: a locally optimal tour Variables: a stack of triples , where is a vertex, is the current number of edges in the trail, and is the current trail gain, the sequence of vertices in the current alternating trail, the best set of exchange edges found for current tour, and its corresponding gain