2026-07-26T21:06:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6639 2024-03-06T10:38:34Z ddc:004 open_access

Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs Marx, Dániel Salmasi, Ario Sidiropoulos, Anastasios asymmetric TSP approximation algorithms nearly-embeddable graphs Held-Karp LP exponential time hypothesis 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 polynomial-time constant-factor approximations on planar graphs and more generally graphs of constant orientable genus. This result was extended to non-orientable genus by Erickson and Sidiropoulos [SoCG, 2014]. We show that for any class of nearly-embeddable graphs, ATSP admits a polynomial-time constant-factor approximation. More precisely, we show that for any fixed non-negative k, there exist positive alpha and beta, such that ATSP on n-vertex k-nearly-embeddable graphs admits an alpha-approximation in time O(n^beta). The class of k-nearly-embeddable graphs contains graphs with at most k apices, k vortices of width at most k, and an underlying surface of either orientable or non-orientable 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 Held-Karp 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 k-nearly embeddable graphs) requires time n^{Omega(k)}, assuming the Exponential-Time 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dániel Marx and Ario Salmasi and Anastasios Sidiropoulos 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.16 urn:nbn:de:0030-drops-66391 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.16 eng https://creativecommons.org/licenses/by/3.0/legalcode