Fine-Grained Complexity Analysis of Two Classic TSP Variants

We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity.  Our first set of results is motivated by the Bitonic TSP problem: given a set of n points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamic-programming exercise to solve this problem in O(n^2) time. While the near-quadratic dependency of similar dynamic programs for Longest Common Subsequence and Discrete Frechet Distance has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves bitonic TSP in O(n log^2 n) time and its bottleneck version in O(n log^3 n) time. In the more general pyramidal TSP problem, the points to be visited are labeled 1,...,n and the sequence of labels in the solution is required to have at most one local maximum. Our algorithms for the bitonic (bottleneck) TSP problem also work for the pyramidal TSP problem in the plane.  Our second set of results concerns the popular k-OPT heuristic for TSP in the graph setting. More precisely, we study the k-OPT decision problem, which asks whether a given tour can be improved by a k-OPT move that replaces k edges in the tour by k new edges. A simple algorithm solves k-OPT in O(n^k) time for fixed k. For 2-opt, this is easily seen to be optimal. For k=3 we prove that an algorithm with a runtime of the form O-Tilde(n^{3-\eps}) exists if and only if All-Pairs Shortest Paths in weighted digraphs has such an algorithm. For general k-opt, it is known that a runtime of f(k) n^o(k/ log k) would contradict the Exponential Time Hypothesis. The results for k=2,3 may suggest that the actual time complexity of k-opt is Theta(n^k). We show that this is not the case, by presenting an algorithm that finds the best k-move in O(n^{floor{2k/3} + 1) time for fixed k >= 3. This implies that 4-opt can be solved in O(n^3) time, matching the best-known algorithm for 3-opt. 

Joint work with Mark de Berg, Kevin Buchin, and Gerhard Woeginger.