  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 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 2014].
  We show that for any class of \emph{nearly-embeddable} graphs, ATSP admits a
polynomial-time constant-factor approximation. More precisely, we show that for
any fixed $k\geq 0$, there exist $\alpha, \beta>0$, such that ATSP on
$n$-vertex $k$-nearly-embeddable graphs admits a $\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.
