In combinatorial optimization, Lin–Kernighan is one of the best heuristics for solving the symmetric travelling salesman problem. It belongs to the class of local search algorithms, which take a tour (Hamiltonian cycle) as part of the input and attempt to improve it by searching in the neighbourhood of the given tour for one that is shorter, and upon finding one repeats the process from that new one, until encountering a local minimum. As in the case of the related 2-opt and 3-opt algorithms, the relevant measure of "distance" between two tours is the number of edges which are in one but not the other; new tours are built by reassembling pieces of the old tour in a different order, sometimes changing the direction in which a sub-tour is traversed. Lin–Kernighan is adaptive and has no fixed number of edges to replace at a step, but favours small numbers such as 2 or 3. Derivation For a given instance of the travelling salesman problem, tours are uniquely determined by their sets of edges, so we may as well encode them as such. In the main loop of the local search, we have a current tour and are looking for new tour such that the symmetric difference is not too large and the length of the new tour is less than the length of the current tour. Since is typically much smaller than and , it is convenient to consider the quantity — the gain of using when switching from — since : how much longer the current tour is than the new tour . Naively -opt can be regarded as examining all with exactly elements ( in but not in , and another in but not in ) such that is again a tour, looking for such a set which has . It is however easier to do those tests in the opposite order: first search for plausible with positive gain, and only second check if is in fact a tour. Define a trail in to be alternating (with respect to ) if its edges are alternatingly in and not in , respectively. Because the subgraphs and are -regular, the subgraph will have vertices of degree , , and only, and at each vertex there are as many incident edges from as there are from . Hence (essentially by Hierholzer's algorithm for finding Eulerian circuits) the graph decomposes into closed alternating