Abstract
We analyze two classic variants of the Traveling Salesman Problem using the toolkit of finegrained 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 dynamicprogramming exercise to solve this problem in O(n^2) time. While the nearquadratic dependency of similar dynamic programs for Longest Common Subsequence and Discrete Fréchet 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 kopt heuristic for tsp in the graph setting. More precisely, we study the kopt decision problem, which asks whether a given tour can be improved by a kopt move that replaces k edges in the tour by k new edges. A simple algorithm solves kopt in O(n^k) time for fixed k. For 2opt, this is easily seen to be optimal. For k = 3 we prove that an algorithm with a runtime of the form ~O(n^{3epsilon}) exists if and only if AllPairs Shortest Paths in weighted digraphs has such an algorithm. For general kopt, 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 kopt is Theta(n^k). We show that this is not the case, by presenting an algorithm that finds the best kmove in O(n^{lfoor 2k/3 rfloor +1}) time for fixed k >= 3. This implies that 4opt can be solved in O(n^3) time, matching the bestknown algorithm for 3opt. Finally, we show how to beat the quadratic barrier for k = 2 in two important settings, namely for points in the plane and when we want to solve 2opt repeatedly
BibTeX  Entry
@InProceedings{deberg_et_al:LIPIcs:2016:6277,
author = {Mark de Berg and Kevin Buchin and Bart M. P. Jansen and Gerhard Woeginger},
title = {{FineGrained Complexity Analysis of Two Classic TSP Variants}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {5:15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6277},
URN = {urn:nbn:de:0030drops62770},
doi = {10.4230/LIPIcs.ICALP.2016.5},
annote = {Keywords: Traveling salesman problem, finegrained complexity, bitonic tours, kopt}
}
Keywords: 

Traveling salesman problem, finegrained complexity, bitonic tours, kopt 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

17.08.2016 