Bonnet, Édouard ;
Iwata, Yoichi ;
Jansen, Bart M. P. ;
Kowalik, Lukasz
FineGrained Complexity of kOPT in BoundedDegree Graphs for Solving TSP
Abstract
The Traveling Salesman Problem asks to find a minimumweight Hamiltonian cycle in an edgeweighted complete graph. Local search is a widelyemployed strategy for finding good solutions to TSP. A popular neighborhood operator for local search is kopt, which turns a Hamiltonian cycle C into a new Hamiltonian cycle C' by replacing k edges. We analyze the problem of determining whether the weight of a given cycle can be decreased by a kopt move. Earlier work has shown that (i) assuming the Exponential Time Hypothesis, there is no algorithm that can detect whether or not a given Hamiltonian cycle C in an nvertex input can be improved by a kopt move in time f(k) n^o(k / log k) for any function f, while (ii) it is possible to improve on the bruteforce running time of O(n^k) and save linear factors in the exponent. Modern TSP heuristics are very successful at identifying the most promising edges to be used in kopt moves, and experiments show that very good global solutions can already be reached using only the topO(1) most promising edges incident to each vertex. This leads to the following question: can improving kopt moves be found efficiently in graphs of bounded degree? We answer this question in various regimes, presenting new algorithms and conditional lower bounds. We show that the aforementioned ETH lower bound also holds for graphs of maximum degree three, but that in boundeddegree graphs the best improving kmove can be found in time O(n^((23/135+epsilon_k)k)), where lim_{k > infty} epsilon_k = 0. This improves upon the bestknown bounds for general graphs. Due to its practical importance, we devote special attention to the range of k in which improving kmoves in boundeddegree graphs can be found in quasilinear time. For k <= 7, we give quasilinear time algorithms for general weights. For k=8 we obtain a quasilinear time algorithm when the weights are bounded by O(polylog n). On the other hand, based on established finegrained complexity hypotheses about the impossibility of detecting a triangle in edgelinear time, we prove that the k = 9 case does not admit quasilinear time algorithms. Hence we fully characterize the values of k for which quasilinear time algorithms exist for polylogarithmic weights on boundeddegree graphs.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs:2019:11144,
author = {{\'E}douard Bonnet and Yoichi Iwata and Bart M. P. Jansen and Lukasz Kowalik},
title = {{FineGrained Complexity of kOPT in BoundedDegree Graphs for Solving TSP}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {23:123:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11144},
URN = {urn:nbn:de:0030drops111444},
doi = {10.4230/LIPIcs.ESA.2019.23},
annote = {Keywords: traveling salesman problem, kOPT, bounded degree}
}
06.09.2019
Keywords: 

traveling salesman problem, kOPT, bounded degree 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 