TADM2E 9.3

We assume that the graph is unweighted, i.e. that all edges have weight 1. We also assume that there is at least one edge in the graph.

• First we determine the length of the shortest TSP tour:
  • for k = 1 to the number of edges: if the function says that there is a TSP tour of length k, stop. k is now the length of the shortest TSP tour.
• then we loop over all edges:
  • if the graph with the edge removed has a TSP tour of length k (according to the function), remove this edge
  • After this loop we are left with a graph containing the vertices of the original graph connected by a subset of the edges of the original graph. By design of the edge removal criterion, this (reduced) graph contains a TSP tour of length k.

Why will there be only edges left which are part of exactly one TSP tour of length k ?

Consider the set of TSP tours of length k of the original graph (note that this set can have more than one member and each pair of such tours differs by at least one edge). The function we were given evaluates to true as long as the remaining edges in the graph are a superset of at least one of the TSP tours of length k. If a certain edge is part of all remaining TSP tours (compatible with the remaining edges in the graph), we can not remove it. If the edge is only part of certain TSP tours, we can remove the edge but also reduce the list of still possible TSP tours of length k. Because all possible TSP tours differ by at least one edge from each other, the list of possible TSP tours (of length k) at the end will only have (at most) one member and all edges not in this tour will have been removed from the graph.

Which particular tour we find depends on the order we visit the edges.