2016/01/06 by Dániel Marx, Marx, Daniel, Ario Salmasi +3 · 1 citation
Computer Science · Engineering · Social Sciences · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Sex work and related issues #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1601.01372
openalex publication_date 2016/01/06 · openalex created_date 2022/09/05 · openalex updated_date 2026/07/28
In the Asymmetric Traveling Salesperson Problem (ATSP) the goal is to find a\nclosed walk of minimum cost in a directed graph visiting every vertex. We\nconsider the approximability of ATSP on topologically restricted graphs. It has\nbeen shown by [Oveis Gharan and Saberi 2011] that there exists polynomial-time\nconstant-factor approximations on planar graphs and more generally graphs of\nconstant orientable genus. This result was extended to non-orientable genus by\n[Erickson and Sidiropoulos 2014].\n We show that for any class of \nearly-embeddable graphs, ATSP admits a\npolynomial-time constant-factor approximation. More precisely, we show that for\nany fixed k\≥ 0, there exist \α, \β>0, such that ATSP on\nn-vertex k-nearly-embeddable graphs admits a \α-approximation in time\nO(n^\β). The class of k-nearly-embeddable graphs contains graphs with at\nmost k apices, k vortices of width at most k, and an underlying surface\nof either orientable or non-orientable genus at most k. Prior to our work,\neven the case of graphs with a single apex was open. Our algorithm combines\ntools from rounding the Held-Karp LP via thin trees with dynamic programming.\n We complement our upper bounds by showing that solving ATSP exactly on graphs\nof pathwidth k (and hence on k-nearly embeddable graphs) requires time\nn\Ω(k), assuming the Exponential-Time Hypothesis (ETH). This is\nsurprising in light of the fact that both TSP on undirected graphs and Minimum\nCost Hamiltonian Cycle on directed graphs are FPT parameterized by treewidth.\n