Marx, Dániel ;
Salmasi, Ario ;
Sidiropoulos, Anastasios
ConstantFactor Approximations for Asymmetric TSP on NearlyEmbeddable Graphs
Abstract
In the Asymmetric Traveling Salesperson Problem (ATSP) the goal is to find a closed walk of minimum cost in a directed graph visiting every vertex. We consider the approximability of ATSP on topologically restricted graphs. It has been shown by Oveis Gharan and Saberi [SODA, 2011] that there exists polynomialtime constantfactor approximations on planar graphs and more generally graphs of constant orientable genus. This result was extended to nonorientable genus by Erickson and Sidiropoulos [SoCG, 2014].
We show that for any class of nearlyembeddable graphs, ATSP admits a polynomialtime constantfactor approximation. More precisely, we show that for any fixed nonnegative k, there exist positive alpha and beta, such that ATSP on nvertex knearlyembeddable graphs admits an alphaapproximation in time O(n^beta). The class of knearlyembeddable graphs contains graphs with at most k apices, k vortices of width at most k, and an underlying surface of either orientable or nonorientable genus at most k. Prior to our work, even the case of graphs with a single apex was open. Our algorithm combines tools from rounding the HeldKarp LP via thin trees with dynamic programming.
We complement our upper bounds by showing that solving ATSP exactly on graphs of pathwidth k (and hence on knearly embeddable graphs) requires time n^{Omega(k)}, assuming the ExponentialTime Hypothesis (ETH). This is surprising in light of the fact that both TSP on undirected graphs and Minimum Cost Hamiltonian Cycle on directed graphs are FPT parameterized by treewidth.
BibTeX  Entry
@InProceedings{marx_et_al:LIPIcs:2016:6639,
author = {D{\'a}niel Marx and Ario Salmasi and Anastasios Sidiropoulos},
title = {{ConstantFactor Approximations for Asymmetric TSP on NearlyEmbeddable Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {16:116:54},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6639},
URN = {urn:nbn:de:0030drops66391},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.16},
annote = {Keywords: asymmetric TSP, approximation algorithms, nearlyembeddable graphs, HeldKarp LP, exponential time hypothesis}
}
2016
Keywords: 

asymmetric TSP, approximation algorithms, nearlyembeddable graphs, HeldKarp LP, exponential time hypothesis 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Issue date: 

2016 
Date of publication: 

2016 