The Asymmetric Traveling Salesman Problem \\ on Graphs with Bounded Genus
Shayan Oveis Gharan% \thanks{ Department of Management Science and Engineering
Stanford
Amin Saberi\footnotemark[1]%
We give a constant factor approximation algorithm for the asymmetric traveling salesman problem when the support graph of the solution of the Held-Karp linear programming relaxation has orientable bounded genus. Our result also implies Goddyn's conjecture on the existence of thin trees in graphs with orientable bounded genus.
Cycle_Deletion.tex
%\documentclass{article}
%\usepackage{tikz}
%\usetikzlibrary{%
%decorations.fractals,%
%decorations.shapes,%
%decorations.text,%
%decorations.pathmorphing,%
%decorations.pathreplacing,%
%decorations.footprints,%
%decorations.markings}
%\pagestyle{empty}

%
%\oddsidemargin -.5in

%\def \Pointsize {1.4pt}
%\begin{document}

%\begin{figure}

%\def \Pointsize {1.4pt}
\begin{tikzpicture}[scale=.6]
\draw [fill,color=black!8!white!92] (-5.5,3) rectangle (3.5,-2);
\draw [fill,color=black!8!white!92,decorate,decoration={zigzag,amplitude=1.5mm,segment length=5mm,post length=0mm}] (-5.7,2.8) rectangle (-.7,-1.7) (1.7,2.8) rectangle (3.7,-1.8);
\draw [line width=1.2pt](-5.5,3) -- (3.5,3) (-5.5,-2) -- (3.5,-2);
%\draw [color=black!8!white!92,fill]  (-5.5,.5) ellipse (.3cm and 2.5cm);

%\draw [color=black!25!white!75,fill] (3.5,.5) ellipse (.3cm and 2.5cm);
%\draw [color=black,line width=1.2pt] (3.5,3) arc (90:270:.3cm and 2.5cm) (-5.5,3) arc (90:270:.3cm and 2.5cm);
%\draw [color=black,dashed] (3.5,-2) arc (-90:90:.3cm and 2.5cm) (-5.5,-2) arc (-90:90:.3cm and 2.5cm);

\draw [color=red] (0,3) arc (90:270:.5cm and 2.5cm);
\draw [color=red,dashed] (0,-2) arc (-90:90:.5cm and 2.5cm);

tikzstyle{every node}=[shape=circle,color=red,fill=red,inner sep=\Pointsize];
\draw [color=red,fill]  (0,.5) +(185:.5cm and 2.5cm)  circle (.12cm);
\draw [color=red,fill]  (0,.5) +(125:.5cm and 2.5cm)  circle (.12cm);
\draw [color=red,fill]  (0,.5) +(153:.5cm and 2.5cm)  circle (.12cm);
\draw [color=red,fill]  (0,.5) +(230:.5cm and 2.5cm)  circle (.12cm);

\tikzstyle{every node}=[draw,shape=circle,fill=black,inner sep=\Pointsize];

\path (-2.5,0) node (v0) {$$};
\path (v0) +(.5,2) node (v1) {$$};
\path (v0) +(0,-1.5) node (v2) {$$};
\path (v1) +(4,0) node (v3) {$$} edge (v1);
\path (v0) +(4.5,0) node (v4) {$$} edge (v3) edge (v1) edge (v2);
\path [dashed] (v2) +(4.5,0) node (v5) {$$} edge (v0);
\path (v0) +(-1,0) node (v6) {$$} edge (v1) edge (v2);


\draw [color=black] (v6)-- +(-1,0) (v3)-- +(1,0) (v4)-- +(1,0);
\draw [dashed] (v0)-- +(-2,-1.5) (v5)-- +(1,0)  (v5) -- +(1,1);
\draw (v6) arc (180:90:.5cm and 3cm);
\draw [dashed] (v0) arc (0:90:.5cm and 3cm);

\draw [->,>=latex,line width=3.5pt] (4,0) -- (6,0);

\begin{scope}[xshift=12cm]
\draw [fill,color=black!8!white!92] (-5.5,3) rectangle (-1,-2) (1,3) rectangle (3.5,-2);
%\draw [fill,color=black!8!white!92,decorate,decoration={zigzag,amplitude=1.5mm,segment length=5mm,post length=2.5mm}] (-5.7,2.8) rectangle (-3,-1.9) (2,2.9) rectangle (3.7,-1.9);
\draw [fill,color=black!8!white!92,decorate,decoration={zigzag,amplitude=1.5mm,segment length=5mm,post length=0mm}] (-5.7,2.8) rectangle (-.7,-1.7) (1.7,2.8) rectangle (3.7,-1.8);
\draw [line width=1.2pt] (-5.5,3) -- (-.8,3) (-5.5,-2) -- (-.8,-2) (.8,3)--(3.5,3) (.8,-2)--(3.5,-2);
%\draw [color=black!8!white!92,fill]  (-5.5,.5) ellipse (.3cm and 2.5cm);

\tikzstyle{every node}=[draw,shape=circle,fill=black,inner sep=\Pointsize];
\path (-2.5,0) node (v0) {$$};
\path (v0) +(.5,2) node (v1) {$$};
\path (v0) +(0,-1.5) node (v2) {$$};
\path (v1) +(4,0) node (v3) {$$} ;
\path (v0) +(4.5,0) node (v4) {$$} edge (v3) ;
\path [dashed] (v2) +(4.5,0) node (v5) {$$} ;
\path (v0) +(-1,0) node (v6) {$$} edge (v1) edge (v2);

\draw [color=black] (v6)-- +(-1,0) (v3)-- +(1,0) (v4)-- +(1,0);
\draw [dashed] (v0)-- +(-2,-1.5) (v5)-- +(1,0)  (v5) -- +(1,1);
\draw (v6) arc (180:90:.5cm and 3cm);
\draw [dashed] (v0) arc (0:90:.5cm and 3cm);

\draw [gray,fill] (-.8,.5) ellipse (.5cm and 2.5cm) (.8,.5) ellipse (.5cm and 2.5cm);
\end{scope}

\end{tikzpicture} 


%\begin{figure}
%\begin{tabular}{lllll}
%\begin{tabular}{c}
%\begin{tikzpicture}
%\tikzstyle{every node}=[draw, shape=circle,color=black,fill=black,inner sep=\Pointsize];
%\path (0:0cm) node (v0) {$$};
%\path (90:1.5cm) node (v1)  {$$} edge (v0);
%\path (210:1.5cm) node(v2) {$$} edge (v0);
%\path (-30:1.5cm) node(v3) {$$} edge (v0);
%\path (v1) +(0:2.5cm) node(v4) {$$};
%\path (v1) +(0:-2.5cm) node(v5) {$$};
%\path [yshift=-.75cm] (0:2.5cm) node(v6) {$$};
%\node [label=above:$a$] at (v1) {};
%\node [label=below:$b$] at (v2) {};
%\node [label=below:$c$] at (v3) {};

%\draw  (v1) -- (v4) (v1) -- (v5) (v2)--(v5) (v3) -- (v6)(v4)--(v6);
%\draw [color=blue] (v1) -- (v2) (v2)--(v3) (v3)--(v1) ;
%\tikzstyle{every node}=[draw, shape=circle,color=red,fill=red,inner sep=\Pointsize];
%\path (45:.55cm) node(u0) {$$};
%\path (135:.55cm) node(u1) {$$};
%\path (270:.55cm) node(u2) {$$};
%\path (u0) +(0:1.3cm) node(u3) {$$};
%\path (u1) +(-20:-1cm) node(u4) {$$};

%\draw [color=red] (u0)--(u1) (u1)--(u2) (u2)--(u0) (u0)--(u3) (u1)--(u4) (u3)-- +(0:1.3cm)
%(u3)-- +(90:1.5cm) (u3)-- +(270:1.5cm) (u4)-- +(90:1.1cm) (u4)-- +(210:1cm) (u2)-- +(270:.5cm);
%\end{tikzpicture} 
%\end{tabular}&
%\begin{tabular}{c}
%\begin{tikzpicture}
%\draw [->,>=latex,line width=3.5pt] (0,0) -- (1,0);
%\end{tikzpicture}
%\end{tabular}&
%\begin{tabular}{c}
%\begin{tikzpicture}
%\tikzstyle{every node}=[draw, shape=circle,color=black,fill=black,inner sep=\Pointsize];
%\path (0:0cm) node (v0) {$$};
%\path (90:1.5cm) node (v1) {$$};
%\path (210:1.5cm) node(v2) {$$};
%\path (-30:1.5cm) node(v3) {$$};
%\node [label=above:$a'$] at (v1) {};
%\node [label=below:$b'$] at (v2) {};
%\node [label=below:$c'$] at (v3) {};

%\draw (v0) -- (v1) (v0) -- (v2) (v0) -- (v3) ;
%\draw [color=blue] (v1)--(v2) (v2)--(v3) (v3)--(v1);
%\tikzstyle{every node}=[draw, shape=circle,color=red,fill=red,inner sep=\Pointsize];
%\path (45:.55cm) node(u0) {$$};
%\path (135:.55cm) node(u1) {$$};
%\path (270:.55cm) node(u2) {$$};
%\draw [color=red] (u0)--(u1) (u1)--(u2) (u2)--(u0) (u0) -- +(45:.5cm) (u1)-- +(135:.5cm) (u2)-- +(270:.5cm);

%\end{tikzpicture}\\
%\begin{tikzpicture}
%\tikzstyle{every node}=[draw, shape=circle,color=black,fill=black,inner sep=\Pointsize];
%\path (90:1.5cm) node (v1) {$$};
%\path (210:1.5cm) node(v2) {$$};
%\path (-30:1.5cm) node(v3) {$$};
%\path (v1) +(0:2.5cm) node(v4) {$$};
%\path (v1) +(0:-2.5cm) node(v5) {$$};
%\path [yshift=-.75cm] (0:2.5cm) node(v6) {$$};
%\node [label=above:$a''$] at (v1) {};
%\node [label=below:$b''$] at (v2) {};
%\node [label=below:$c''$] at (v3) {};

%\draw  (v1) -- (v4) (v1) -- (v5) (v2)--(v5) (v3) -- (v6)(v4)--(v6);
%\draw [color=blue] (v1) -- (v2) (v2)--(v3) (v3)--(v1) ;
%\tikzstyle{every node}=[draw, shape=circle,color=red,fill=red,inner sep=\Pointsize];
%\path (90:.25cm) node(u0) {$$};
%\path (u0) +(0:1.7cm) node(u3) {$$};
%\path (u1) +(-20:-1cm) node(u4) {$$};

%\draw [color=red] (u0)--(u3) (u0)--(u4)  (u3)-- +(0:1cm)
%(u3)-- +(90:1.5cm) (u3)-- +(270:1.5cm) (u4)-- +(90:1.1cm) (u4)-- +(210:1cm) (u0)-- +(270:1.2cm);

%\end{tikzpicture}
%\end{tabular} &
%\begin{tabular}{c}
%\begin{tikzpicture}
%\draw [->,>=latex,line width=3.5pt] (0,0) -- (1,0);
%\end{tikzpicture}
%\end{tabular}&

%\begin{tabular}{c}
%\begin{tikzpicture}
%\tikzstyle{every node}=[draw, shape=circle,color=black,fill=black,inner sep=\Pointsize];
%\path (0:0cm) node (v0) {};
%\path (0:1.5cm) node (v1) {} edge (v0) edge [bend left=60] (v0) edge [bend right=60] (v0);
%\tikzstyle{every node}=[draw, shape=circle,color=red,fill=red,inner sep=\Pointsize];
%\path (15:.75cm) node (u0) {};
%\path (-15:.75cm) node (u1) {} edge [color=red] (u0);
%\path (0:2.5cm) node (u2) {} edge [color=red,bend left] (u1) edge [color=red,bend right] (u0);
%%\end{tikzpicture}\\
%\begin{tikzpicture}
%\path (0:0) node (alaki) {};
%\begin{scope}[yshift=-3cm]
%\tikzstyle{every node}=[draw, shape=circle,color=black,fill=black,inner sep=\Pointsize];
%\path (0:0cm) node (v0) {};
%\path  +(35:1.9cm) node(v4) {$$} edge (v0);
%\path  +(145:1.9cm) node(v5) {$$} edge [bend left=45] (v0) edge [bend right=45] (v0);
%\path [yshift=-.75cm] (0:1.5cm) node(v6) {$$} edge (v0) edge (v4);

%\tikzstyle{every node}=[draw, shape=circle,color=red,fill=red,inner sep=\Pointsize];
%\path (0:1cm) node (u0) {};
%\path (145:1cm) node (u1) {};
%\draw [color=red] (u0)-- +(0:.75cm) (u0)-- +(90:1cm) (u0) -- +(270:.75cm) (u1) -- +(90:.75cm) (u1)-- +(210:.75cm);
%\end{scope}
%\end{tikzpicture}

%
%\end{tabular}
%\end{tabular}
%\end{figure}
%\end{document}
bg-18.tex
\documentclass[extras,11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath}  %for \align
\usepackage{amssymb}
\usepackage{epsfig}
\usepackage{pxfonts}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{color}
\usepackage{tikz}
%\usepackage{extra} %for lp
%\usepackage[numbered]{algo}
\usepackage{hyperref}
\usetikzlibrary{%
decorations.fractals,%
decorations.shapes,%
decorations.text,%
decorations.pathmorphing,%
decorations.pathreplacing,%
decorations.footprints,%
decorations.markings}

\renewcommand\rmdefault{cmr}
\renewcommand\sfdefault{cmss}
\renewcommand\ttdefault{cmtt}
%\numberwithin{algorithm}{section}
\newcommand{\theHalgorithm}{\arabic{algorithm}}
\newcommand{\INPUT}{\item[{\bf Input:}]}
\newcommand{\OUTPUT}{\item[{\bf Output:}]}
%\newcommand{\RETURN}{\item[{\bf Return:}]}


%\setlength{\textheight}{8.8in} \setlength{\textwidth}{6.2in}
%\setlength{\topmargin}{-0.5cm} \setlength{\evensidemargin}{1pt}
%\setlength{\oddsidemargin}{1pt} \setlength{\headsep}{10pt}
%\setlength{\parindent}{0pt} \setlength{\parskip}{1ex}



\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{property}[theorem]{Property}
\newtheorem{problem}[theorem]{Problem}

\newenvironment{proof}{\noindent{\bf Proof}:}{$\hfill \Box$\\}

\def \bx{\textbf{\itshape x$\,$}}
\def \HK{{\textrm{OPT}_{\textrm{HK}}}}
\def \genus {\gamma}
\def \girth {g}
\def\surface {\Sigma}
\newcommand{ \app}[1]{\frac {16\genus(4+2\log{(2\genus+3/2))}}{#1}}
\def\Pointsize {1.4pt}
\begin{document}

\title{The Asymmetric Traveling Salesman Problem  \\     on Graphs with Bounded Genus}


\author{
Shayan Oveis Gharan%
    \thanks{ Department of Management Science and Engineering, Stanford University, Stanford, CA 94305. Email:\protect\url{{shayan,saberi}@stanford.edu}.}
\and
  Amin Saberi\footnotemark[1]%
}

\date{}

\maketitle

\begin{abstract}
We give a constant factor approximation algorithm for the asymmetric
traveling salesman problem when the support graph of the solution of the 
Held-Karp linear programming relaxation has orientable bounded genus. Our result
also implies Goddyn's conjecture on the existence of thin trees in
graphs with orientable bounded genus.
\end{abstract}

\setcounter{page}0
\thispagestyle{empty}
\clearpage


\section{Introduction}

The Symmetric Traveling Salesman Problem (STSP) has been studied
extensively on planar or low-genus metrics. In particular,
polynomial time approximation schemes have been found for Euclidean
TSP \cite{aroraeuclidean}, when the distances are shortest paths in
a planar graph \cite{Papadimitriou:planartsp,Arora:planartsp,kleintsp}, or a
bounded-genus graph \cite{Demaine:boundedgenus}.

We give the first constant approximation algorithm for the
Asymmetric Traveling Salesman Problem (ATSP) for metrics that are
shortest path distances in a weighted directed graph with a bounded
orientable genus. This is a very natural special case: consider a
metric obtained by shortest path distances in a city with one way
streets and a constant number of bridges and underpasses.



The result  is in fact more general: we can obtain constant factor
approximation algorithms when the underlying graph of the fractional
solution of the Held-Karp linear relaxation can be embedded on an
orientable surface with bounded genus. It is easy to see that this
is a less strict condition. In fact, it is known that the corner
points of the Held-Karp relaxation polytope define very sparse
graphs \cite{goemans06} and  in practice, they often turn out to be
planar\footnote{Unfortunately, this is not the case in general: one
can use the construction of Carr and Vempala
\cite{vempala:4/3integralitygap} to construct corner points of the
LP relaxation whose underlying graph has arbitrarily high genus.}.% of the same order as the number of vertices. % $O(\gamma(n))$, where $n$ is the number of vertices.

Our algorithm is  based on rounding the solution of the Held-Karp
linear programming  relaxation. Therefore, it also gives a constant
upper bound on the integrality gap of the LP. Note that the
best-known constructions for lower bounding the integrality gap, by
Charikar et al. \cite{charikar:integralitygap}, are based on
directed  planar graphs.

For general metrics, Frieze et al.~\cite{atsplogn}
found a $\log_2{n}$-approximation algorithm. After  subsequent
improvements by \cite{Blaser02,Kaplan05,FeigeS07}, Asadpour et al.
\cite{atsploglogn}  obtained an
$O(\log{n}/\log{\log{n}})$-approximation algorithm.


Similar to Asadpour et al. \cite{atsploglogn},  our results are
based on finding a thin tree of small cost in the fractional
solution. However, for finding this thin tree we use  very different
techniques stemming from the graph embedding literature. It is worth
noting that the conjecture on the existence of such thin trees was
made initially in that context. For a more detailed discussion see
Section \ref{sec:goddyn}.


First, we observe that  the connection used in \cite{atsploglogn}
between ATSP and thin trees is more concrete: in order to find a
constant factor approximation algorithm for ATSP, it is sufficient
to find a $c/k$-thin spanning tree in a $k$-edge connected graph for
some constant $c$. Remember that a tree is $\epsilon$-thin with
respect to $G$, if it does not contain more than an
$\epsilon$-fraction of edges of $G$ across any cut.

The main result of the paper is to find a polynomial-time algorithm
for finding an $f(\genus)/k$-thin tree in a $k$-edge connected graph
of genus $\genus$. The embedding of the graph and its particular
geometric dual play an essential role in finding a thin tree and
providing a certificate for its thinness.

In particular, our most basic tool for
establishing the thinness of a tree $T$ in $G$ is to relate it to
the pairwise distance of its corresponding edges $T^*$ in the dual
graph $G^*$. If $G^*$ does not have any short cycles and all the
edges of $T^*$ are far apart in $G^*$, then the tree can not contain
too many edges from any cut and therefore it is thin. In Section
\ref{sec:findthintree}, we explain our algorithm for finding such a
tree.

The algorithm proposed in Section \ref{sec:findthintree} is only
useful when the dual graph $G^*$ has high girth.  For  planar graphs
this is not a problem.  The dual of every cutset in $G$ is a cycle
in the dual graph $G^*$. Therefore if $G$ is $k$-edge connected, $G^*$ has
girth at least $k$. This is not necessarily true for graphs with
genus even slightly bigger than zero. In section
\ref{sec:dual-girth}, we show how to remove short cycles from $G^*$
without creating too many connected components in $G$. For doing
this, we need  operations like cutting handles and adding
topological disks that modify the surface on which the graphs are
embedded.

In the Section \ref{sec:final}, we derive a constant approximation
algorithm for ATSP on bounded-genus graphs using the result on thin
trees. Our result on the existence of thin trees in bounded genus
graphs also have implications about no-where zero flows on these
graphs. For that reason our theorem on the existence of thin trees
can be seen as a strengthening of \cite{zhang:jaeger}. Furthermore,
our approach yields a much simpler proof than the  vertex splitting
argument of \cite{zhang:jaeger} that needs extensive case analysis.



%For the ease of notation, we represent the fractional solution with
%a multigraph: for some $k \geq n^2$, construct a multigraph $G$ by
%putting $\lfloor \frac{x_e}{k} \rfloor $ copies of every edge $e$
%between its end points. The resulting graph is at least $k-1$-edge
%connected.
%
%It turns out, (and it is proved using a very delicate argument) that
%
%
%
%Let us explain the algorithm for finding a thin tree starting with
%the special case in which $G$ is planar. Consider $G^*$, the dual of
%$G$. First observe that by Whitney's theorem, . Therefore $G^*$ has girth at
%least $k$.
%
%
%Unfortunately, as far as we know, there is no equivalent version of
%Whitney's theorem in surfaces with genus greater than zero. Indeed,
%even the dual of a graph  with high edge connectivity embedded on a
%torus can have very small cycles. Nevertheless, we will show that
%with small changes, it is possible to get rid of these small cycles.
%In particular, for any graph $G$ embedded on an orientable surface
%with genus $\gamma$, it is possible to find a $k/2$-edge connected
%subgraph $H$, such that $H^*$ has girth $O(k/\gamma)$. The details
%of the algorithm for obtaining $H$ can be found in Section
%\ref{sec:incdualgirth}.
%
%
%In Section \ref{sec:findthintree}, we explain how to find the thin
%tree using the embedding of $H$ and its high girth dual. This is
%possible by iteratively finding long induced paths.
%



%%%%%%Section 2 Preliminaries


\section{Preliminaries}
\label{sec:preliminaries}

In the Asymmetric Traveling Salesman problem (ATSP),  we are given a
set $V$ of $n$ points and a cost function  $c: V \times V
\rightarrow \mathbb{R}^+$. The goal is to find the minimum cost tour
that visits every vertex at least once. Since we can replace every
arc $(u,v)$ in the tour with the shortest path from $u$ to $v$, we
can assume $c$ satisfies the triangle inequality.



In this paper, we refer to multi-graphs (graphs with loops and
parallel edges) simply as graphs. Let $G(V,E)$ be a weighted undirected graph with cost
function $c(e)$,  and $F \subseteq E$ be a collection of edges. We define
$c(F)  :=  \sum_{e \in F} c(e)$.

\begin{definition}
A subset $F\subseteq E$  is $\alpha$-thin with
respect to $G$, if for each set $U\subset V$,
$$|F(U,\overline{U})|\leq \alpha |E(U,\overline{U})|,$$
where $F(U,\overline{U})$ and $E(U,\overline{U})$ are respectively
the sets of edges of $F$ and $E$ that are in the cut  $(U,
\overline{U})$. We say $F$
is $(\alpha, \sigma)$-thin with respect to $G$, if it is
$\alpha$-thin and $c(F) \leq \sigma c(E).$
\end{definition}

Given an instance of ATSP corresponding to the cost function $c: V \times V \rightarrow \mathbb{R}^+$, we can obtain a lower bound on the optimum value by considering the following linear programming relaxation defined on the complete bidirected graph with vertex set $V$:
\begin{eqnarray}
\label{atsplp}
\textrm{min} & & \sum_{a} c(a) x_a \\
\textrm{s.t.} & & \bx(\delta^+(S)) \geq 1 ~~~~~~~~~~~~~~~~~~~\forall S \subset V,  \label{eq:d+} \\
& & \bx(\delta^+(v)) = \bx(\delta^-(v)) =1 ~~~~\forall v \in V, \label{eq:eul}\nonumber \\
& & x_a \geq 0  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~  \forall a \nonumber.
\end{eqnarray}

In the above linear program $\delta^+(S)$ ($\delta^-(S)$) denotes the set of directed edges leaving (entering) $S$ in the bidirectional complete graph on $V$. Also define $\delta(S) = \delta^+(S) \cup \delta^-(S)$.

This linear programming relaxation is known as the Held-Karp
relaxation \cite{HeldKarp70}, and its optimum value, which we denote
by $\HK$, can be computed in polynomial time.

Let $x$ be a feasible  solution of Held-Karp relaxation
(\ref{atsplp}). Our approximation algorithm will be based on
rounding $x$ to an integral solution.  For this rounding, it turns
out that it is sufficient to find a spanning tree that is thin with
respect to $x$.  The following definition is a natural extension
from undirected graph that we incorporate here from
\cite{atsploglogn} with a slight modification.

\begin{definition}
We say that a spanning tree $T$ is $\alpha$-thin with respect to $x$,  if for each set $U\subset V$,
$$|T(U,\overline{U})|\leq \alpha x(\delta(U)),$$
where $T(U,\overline{U})$ is the set of the edges of $T$ that are in
the cut $(U, \overline{U})$.  Also we say that $T$  is
$(\alpha,\sigma)$-thin with respect to $x$, if it is $\alpha$-thin
and moreover it is possible to orient the edges of $T$ into $T^*$
such that
$$c(T^*)\leq \sigma c(x).$$
\end{definition}

%The definition of thinness can be extended naturally to  any
%undirected graph. Let $G(V,E)$ be a weighted graph with cost
%function $c(e)$. A subset $F\subseteq E$  is $\alpha$-thin with
%respect to $G$, if for each set $U\subset V$,
%$|F(U,\overline{U})|\leq \alpha |E(U,\overline{U})|,$ and we say $F$
%is $(\alpha, \sigma)$-thin with respect to $G$, if it is
%$\alpha$-thin and $c(F) \leq \sigma c(G).$


\subsection{Surfaces and graph embedding}
We also need to recall some of the concepts in topological graph theory.
By a {\em surface}, we mean a compact connected 2-manifold without boundary.
It is well known that all surfaces are classified into the sphere with $\genus$ handles (denoted by $S_\genus$) or the crosscaps (denoted by $N_\genus$) and are called orientable and non-orientable surfaces respectively.
 Throughout
this paper by a surface we mean an orientable surface, and all the
theorems have been proved for orientable surfaces.

In the above definition, $\genus$ represents the genus of the surface. An equivalent definition for the genus of an orientable surface is the maximum  number of disjoint simple closed curve which can be cut
from the orientable surface without disconnecting it.

An embedding  of a  graph $G$ into a surface $\surface$, is a
homeomorphism $i:G\rightarrow \surface$ of G into $\surface$. %If every
%component of $\Sigma-i(G)$, called a {\em region}, is homeomorphic
%to an open disk then the embedding $i:G\rightarrow \Sigma$ is called
%a {\em 2-cell embedding} and the regions are called the faces of the
%embedding. Associated with every face is a closed walk in $G$.
%Throughout this paper, we might deal with embeddings that are not
%2-cell, in this case  each region may be a combination of several
%faces.
%An  {\em strong embedding} of $G$ is a 2-cell embedding in which every face is a simple cycle of $G$.
The {\em orientable  genus} of a graph $G$ is the minimum $\genus$
such that $G$ has an embedding in $S_\genus$. For
example, planar graphs have genus zero.

Let $G(V,E)$ be a  graph embedded on a surface $\surface$. A set
$S\subseteq E$ on $\surface$ is {\em separating} if $\surface-S$ is
disconnected; otherwise $S$ is called {\em non-separating}. For
instance, the definition of orientable genus implies that any set of
$\genus(\Sigma)+1$ disjoint cycles of $G$ is separating.
%A {\em boundary subgraph} is the boundary of the union of a subset of faces of $G$; for example, every separating cycle is a boundary subgraph.

Suppose that we have  embedded $G$ on a surface $\Sigma$. The {\em
geometric dual} of $G$ on $\Sigma$, $G^*$, is defined similar to the
planar graphs. Particularly, The vertices of $G^*$ correspond to the
faces of $G$. The edges of $G^*$ are in bijective correspondence $e
\rightarrow e^*$ with the edges of $G$, and the edge $e^*$ joins the
vertices corresponding to the faces containing $e$ in $G$.
%Note that
%if $G$ is cellularly embedded in $\Sigma$, $G^*$ will be cellularly
%embedded in $\Sigma$ and it does not have any loops.
For a more
extensive discussion of embeddings of graphs in surfaces, see
\cite{moharthomassen}.






%%%%%Section: Constructing a thin-tree



\section{Constructing a thin-tree}
\label{sec:findthintree}

%In this section we find a polynomial-time
%algorithm for finding a thin spanning tree in a connected graph $G$
%embedded on an orientable surface $\Sigma$ with bounded genus. and
%high dual girth!

Let $G(V,E)$ be a connected graph embedded on an orientable surface,
and $G^*$ be its geometric dual. The dual-girth of $G$, denoted by
$g^*(G)$ is the length of the shortest cycle in $G^*$.
The main result of this section is the following lemma.

\begin{lemma}\label{lem:dual-girth} A connected graph embedded on an orientable surface
with genus $\gamma$ and dual-girth $g*$ has a spanning tree with thinness
$\frac{2\alpha}{g^*}$, where $\alpha =4+\lfloor
2\log_2{(\genus+\frac{3}{2})}\rfloor$. Furthermore, such a tree can
be found in polynomial time.
\end{lemma}

We will prove this lemma in the rest of this section.
First note that
if $g^* =1$, the lemma holds for trivial reasons.
Therefore, without loss of generality assume that $g^*  > 1$. That implies
that no face of $G$ can have two copies of an edge.
In particular,  $G$ does not have any cut edge.

Define the distance of two edges in a graph to be the closest
distance between their endpoints.  Our most basic tool for
establishing the thinness of a tree $T$ in $G$ is to relate it to
the pairwise distance of its corresponding edges $T^*$ in $G^*$. If
$G^*$ does not have any short cycles and all the edges of $T^*$ are
far apart in $G^*$, then the tree can not contain too many edges
from any cut. We will establish that for any subset of
edges:

\begin{lemma}
\label{lem:thinnesstest} Let $F$ be a set of edges in $G$ and $F^*$
be the corresponding edges in the dual. If for some $m \leq g^*(G)$,
the distance between each pair of edges in $F^*$ is at least $m$,
then $F$ is   $\frac{1}{m}$-thin in $G$.
\end{lemma}
\begin{proof}
Consider a cut $S=(U,\overline{U})$ in $G$. Let us start by
showing that $S^*$ is a collection of edge-disjoint cycles
$C_1,C_2,\ldots,C_l$ in $G^*$. This is because the number of edges from $S^*$ incident to a
vertex in $G^*$ is equal to the intersection of
$S$ with its corresponding face in $G$ and that is an even number. Otherwise,
either that face contains two copies of an edge of $S$, or
one could find a path $P$ in that face such that $P\cap
S=\emptyset$, while the endpoints of $P$ are in different sides of
the cut, which are both impossible.



Because the distance of each pair of edges in $F^*$ is at least $m$,
 $F^*$
can not have more than $\max(1,\lfloor length(C_i)/m \rfloor)$ edges
in $C_i$, for $1\leq i\leq l$. Therefore,
$$|F^*| \leq \sum_{i=1}^l \max(1,\lfloor \frac{length(C_i)}{m}\rfloor)= \sum_{i=1}^l \lfloor \frac{length(C_i)}{m}\rfloor \leq \frac{|S^*|}{m}.$$
Note that the equality holds by the assumption $length(C_i)\geq
g^*\geq m$. Thus the number of edges of $F$ in the cut
$(U,\overline{U})$ is no more than $\lfloor
|(U,\overline{U})|/m\rfloor$ and $F$ is a $1/m$-thin.
\end{proof}


Considering the above Lemma, our goal will be to find a set of edges
in $G^*$ that are sufficiently far. We will do this by finding long
threads iteratively and selecting one edge from each thread.

A {\em thread} in a graph $G$ is a maximal subgraph of $G$ which is
\begin{itemize}
\item a path whose internal vertices all have degree $2$ in $G$
and its endpoints have degree at least 2, or
\item a cycle in which
all vertices except possibly one have degree $2$.
\end{itemize}


\begin{algorithm}
\caption{Finds a thin tree in a graph with large dual-girth}
\label{alg:computethinset}
\begin{algorithmic}[1]
\INPUT A connected graph $G$ embedded on an orientable surface with genus $\genus$, and its dual $G^*$ with girth $g^*$.
\OUTPUT A spanning tree $T$ with thinness at least
$\girth^*/2\alpha$. \STATE $F^* \leftarrow \emptyset$
\WHILE {there exists an edge in $G^*$}% do the following step.
\STATE Find a thread $P$ of length at least $\girth^*/\alpha$ in
$G^*$. \STATE Add the middle edge of $P$ to $F^*$ and remove it from
$G^*$. \STATE \label{algstep:degreeonedeletion} Iteratively delete
all the degree one vertices with their incident edges. \ENDWHILE
\RETURN A spanning tree $T \subseteq F$, where $F$ is the set of
edges corresponding to $F^*$ in $G$.
\end{algorithmic}
\end{algorithm}


 Let us start by showing the existence of long threads. That is a
straightforward application of the result of Goddyn et al. \cite{goddyn:largegirth}.

\begin{lemma}
\label{lem:longthreadexist} A graph  with minimum degree $2$ and
girth $\girth$, embedded on a surface with genus $\genus$ has a
thread of length at least $\girth/\alpha$.
\end{lemma}


\begin{proof}
Let $H$ be a graph satisfying the conditions of the theorem and $H'$
be the graph obtained by iteratively replacing the vertices of
degree $2$ in $H$ with an edge.
In other words, let $H'$ be the graph obtained by replacing every thread
in $H$ by an edge.
By Goddyn et al.
\cite[Theorem 3.2]{goddyn:largegirth}, every graph with minimum degree 3 embedded
on an orientable surface with genus $\genus$ has a cycle of length at most
$\alpha$.  Therefore $H'$ has a cycle of length at most $\alpha$. Now it is
easy to see that at least one of the edges of that cycle is obtained
from a thread of length at least $\frac{\girth}{\alpha}$ in $H$.
\end{proof}

Because of the above lemma, Algorithm \ref{alg:computethinset} terminates in polynomial time.
The algorithm has an equivalent description in terms of the original
graph $G$. Roughly speaking, in each iteration, we find a collection
of consecutive parallel edges,  add the middle edge from that
collection to $F$ and contract the end points. The
embedding is crucial for the execution of this procedure because it
provides a notion of a middle edge, and the notion of consecutive
parallel edges (parallel edges that form a face).
%
%It is important to note that generally, the iterative procedure that finds parallel edges, chooses one and contracts, does not necessarily create a thin tree.


It is also worth noting that $|F|$  may end up being bigger than $|V(G)| - 1$ in an execution of Algorithm  \ref{alg:computethinset}. This is because a thread in $G^*$ may be equivalent to a  collection of parallel {\em loops}.
The next lemma immediately proves Lemma \ref{lem:dual-girth}.

\begin{lemma}
\label{lem:faredgeselection}  The set $F$ computed in Algorithm
\ref{alg:computethinset} is connected and spanning in $G$.
Furthermore, the pairwise distance of the edges of $F^*$ in $G^*$ is
at most $\girth^*/2\alpha$.
\end{lemma}
\begin{proof}
For the proof of the first statement, consider a non-empty cut
$S=(U,\overline{U})$ in $G$, and let $S^*$ be its dual. As we argued
in the proof of Lemma \ref{lem:thinnesstest},  $S^*$ is a collection
of cycles. It is also easy to see that Algorithm
\ref{alg:computethinset} selects at least one edge from each cycle.


For the second statement, first observe that after adding an edge
$e$ to $F^*$, the algorithm immediately removes all the edges that
are of distance less than $g^*/2\alpha$ from $e$. This is because
all these edges are a part of the thread and therefore they are
deleted sequentially.

Furthermore, although each iteration of the while loop may  increase the
distance of some pairs of edges, it never increases the distance of
two edges that are closer than $g^*/\alpha$. Therefore, the distance
of any pairs of edges that are closer than $g^*/ \alpha$ remains the
same until one of them is deleted.
\end{proof}





%%%%%%Section Increasing the girth of dual graph


\section{Increasing the girth of dual graph}
\label{sec:dual-girth}
Let  $G(V,E)$ be a planar graph and $G^*$ be its geometric
dual.
In the
previous section we showed that the girth of $G^*$ plays an important role in finding
a thin spanning tree in $G$.
By Whitney's theorem \cite{whitney:planargraphs}, $S\subseteq E$ is a cutset
(minimal cut) in a {\em planar} graph $G$ if and only if $S^*$ is a cycle in $G^*$.
Therefore, if $G$ is planar and $k$-edge connected, the girth of $G^*$ will be at
least $k$.  Unfortunately, this relation does not hold for non-planar graphs as their dual may have very small cycles.

In the rest of this section we show that we can get rid of these small cycles by deleting their edges. Deleting these edges may result in making the graph disconnected. We will try to increase the girth as much as possible while creating only a small number of connected components.


Later, we will find a thin tree in every connected component and merge them into a spanning tree using an arbitrary set of edges from the original graph. Since the number of connected components is small, this is possible with only a small loss in the thinness of the final spanning tree. In fact, in the statement of Theorem \ref{thm:constantthintree}, the $O(\sqrt{\genus})$ dependence of the thinness on the genus of the surface comes from the   balance between the number of connected components at the end of the procedure with the girth of the final graph in Lemma \ref{lem:smallconlargegirth}.


\begin{lemma}
\label{lem:smallconlargegirth}
Let $G$ be a $k$-edge connected graph embedded on an orientable surface with genus $\genus > 0$, and $G^*$ its geometric dual. There is a polynomial time algorithm that deletes some of the edges of $G$, and obtains a new graph $H$ with the dual $H^*$ such that $H$ has  at most $2\sqrt{\genus}$ connected components while $girth(H^*) \geq \frac{k}{3\sqrt{\genus}}$.
\end{lemma}
The algorithm considers each small cycle in $G^*$, and simply deletes its corresponding edges from $G$, and updates $G^*$ accordingly.
\begin{algorithm}
\caption{Constructing a high girth dual}
\label{alg:incdualgirth}
\begin{algorithmic}[1]
\INPUT A $k$-edge connected graph $G$ embedded on a surface with genus $\genus > 0$ and its dual $G^*$.
\OUTPUT A graph $H$ and its dual $H^*$ where $\kappa(H) \leq 2\sqrt{\genus}$ and $girth(H^*)\geq \frac{k}{3\sqrt{\genus}}$.
\WHILE {$girth(G^*) < \frac{k}{3\sqrt{\genus}}$}
\STATE Find a
cycle $C^*$ of length less than $\frac{k}{3\sqrt{\genus}}$ in $G^*$.
\STATE
Delete its corresponding edges from $G$, and update $G^*$ accordingly.
\ENDWHILE
\RETURN $G$ and $G^*$
\end{algorithmic}
\end{algorithm}

To see the effect of this cycle deletion process we use the
following lemma.

\begin{lemma}
\label{lem:cycleremovalproperty} Let $G$ be a non-planar graph
embedded on an orientable surface $\Sigma$ with genus $\genus$, and
$G^*$ its geometric dual. If $C$ is the set of corresponding edges
of a cycle $C^*$ in $G^*$, then either $G-C$ can be embedded on a
surface with smaller genus, or $\kappa(G-C) > \kappa(G)$, where
$\kappa(G)$ is the number of connected components of $G$.
\end{lemma}

\begin{proof}
We define a surgery operation in which the surface $\Sigma$ is cut
along the simple curve defined by $C^*$,  and then  a topological
disk is attached to each side of the cut. We will show how $G-C$ can
be embedded on the resulting surface (or surfaces).

If $C^*$ is a non-separating cycle in $G$, then cutting along $C^*$
and adding the two topological disks removes one of the handles of
$\Sigma$, thus giving rise to a unique connected surface with
smaller genus. The edges of $C$ crossing the curve $C^*$ are removed
from $G$, therefore $G - C$ is embeddable on the new surface. Figure
\ref{fig:cyclecutting}, shows the details of this operation.

\begin{figure}
\centering
\input{Cycle_Deletion}
\caption{Cutting a surface along a non-separating cycle. The red cycle in the
left diagram is a cycle in the dual.
We cut the surface along the cycle, remove the edges that are cut from
the original graph and attach two topological disks
where the cut is made (right diagram).}
\label{fig:cyclecutting}
\end{figure}


If $C^*$ is a separating cycle, then cutting $\Sigma$ along $C^*$,
creates two surfaces $\Sigma_1$ and $\Sigma_2$, where each one
contains a connected component of $G-C$. The sum of  genera of
$\Sigma_1$ and $\Sigma_2$ is $\genus$. Therefore, in this case only
$\kappa(G-C) > \kappa(G)$.

In both cases the dual embedding is obtained by removing the edges
and vertices of the cycle along which the surface is cut and adding
two vertices $c_l$ and $c_r$ to the disks attached to left and right
side of the cut. The edges of the left side of $C^*$ are attached to $c_l$
and the rest of them to $c_r$.
%\caption{Cutting a surface along a non-separating cycle. The surface
%is cut along the red cycle (from the dual graph) in the left
%diagram. The right diagram is the new graph embedded on the
%resulting surface after attaching the topological disks. }
%\label{fig:cyclecutting}
\end{proof}


Roughly speaking, the  above lemma says that by removing the edges
corresponding to a cycle in $G^*$ from  $G$, we will either decrease
its genus or increase its number of connected components. As we will
show next, the number of connected components in the final graph is
bounded and therefore the procedure has to stop after deleting a
bounded number of cycles.

\begin{proof} [{\bf Lemma \ref{lem:smallconlargegirth}}]
We show that the algorithm \ref{alg:incdualgirth} works correctly.
First of all, note that the algorithm eventually terminates, even if
it has to delete all of the edges of  $G$. Hence, it runs in polynomial
time.

Let $H$ be the output of the algorithm and $H^*$ be its dual. When the algorithm terminates, the girth of $H^*$ is at most $\frac{k}{3\sqrt{\genus}}$. Therefore, the only thing we need to prove is that $\kappa(H) \leq 2\sqrt{\genus}$.
%The proof of correctness goes through a contradictory argument.

Suppose that the while loop is finished after $m$  iterations.
Consider the total number of edges deleted during the execution of the algorithm. Since the number of deleted edges in each iteration of the while loop is no more than $\frac{k}{3\sqrt{\genus}}$, at most $\frac{mk}{3\sqrt{\genus}}$ edges have been deleted totally. On the other hand, all the edges between different connected components of $H$ have been deleted in the loop. Because $G$ was $k$-edge connected, there was originally $\frac{\kappa(H) k }{2}$ edges between these components, where all of them have been deleted.  Therefore,
\begin{equation}
\label{eq:edgedeletion}
\frac{\kappa(H) k}{2} \leq \frac{mk}{3\sqrt{\genus}}.
\end{equation}

In order to bound $\kappa(H)$, we need an upper bound on $m$. By Lemma \ref{lem:cycleremovalproperty}, we have
\begin{equation*}
\label{eq:mupperbound}
m \leq \left( \genus(G) - \genus(H) \right) + \left(\kappa(H) - \kappa(G)\right)
\leq \genus + \kappa(H).
\end{equation*}

By combining this with inequality (\ref{eq:edgedeletion}) we get

\begin{eqnarray*}
  \frac{\kappa(H)}{2} \leq \frac{\genus+\kappa(H)}{3\sqrt{\genus}}
& \Rightarrow & \frac{\kappa(H)}{6} \leq \frac{\sqrt{\genus}}{3}.
\end{eqnarray*}
This implies that $\kappa(H) \leq 2\sqrt{\genus}.$
\end{proof}

%\textcolor{red}{Don't you want to describe the limitations of the algorithm?}

%\begin{remark} The above lemma is only applicable in finding a thin tree in graphs
%with bounded genus. This is because in this method, we are only able
%to prove an upperbound on the thinness that is at most the inverse
%of girth of the dual.
%On the other hand, if a graph has high edge connectivity and large
%genus, its dual will have several short cycles and it seems unlikely
%that we can remove them using a method similar to Algorithm
%\ref{alg:incdualgirth}. For example, consider the dual of a complete
%graph of size $n$. The number of vertices of this graph will be of
%$O(n^2)$. Furthermore, the degree of  each vertex in that graph is
%at least 3. Therefore, it will have many cycles with length
%logarithmic in $n$.
%\end{remark}




%%%%%Section: Thin trees, Goddyn's conjecture and ATSP




\section{Thin trees, Goddyn's conjecture and ATSP}
\label{sec:final}

The algorithms presented in sections \ref{sec:findthintree} and \ref{sec:dual-girth} and their analysis imply the following result:

\begin{theorem}
\label{thm:constantthintree} A $k$-edge connected graph embeddable
on an orientable surface with genus $\genus$ has a spanning tree
with thinness $\frac{f(\genus)}{k}$ for some function $f(\genus) =
O(\sqrt{\genus}\log(\genus))$. Such a spanning tree can be found in
polynomial time.
\end{theorem}

\begin{proof}
%First, using Mohar \cite{mohar:embedding}, for a constant $\genus$, there is a  linear time algorithm that finds an embedding of a given graph on that surface, if such an embedding  exists.
%Compute an embedding of $G$  and its dual $G^*$ with respect to that embedding.
If $\genus = 0$, i.e., $G$ is planar then by \cite{whitney:planargraphs}, $g^*$, the girth of $G^*$ will be at
least $k$.  By Lemma \ref{lem:dual-girth}, Algorithm \ref{alg:computethinset} can find a spanning tree in $G$ with thinness $10/k$.

If $\genus > 0$, then run Algorithm \ref{alg:incdualgirth}  to
obtain a subgraph $H$ of $G$ which has by Lemma
\ref{lem:smallconlargegirth} at most $2\sqrt{\genus}$ connected
components while $girth(H^*) \geq \tfrac{k}{3\sqrt{\genus}}$. Again,
use  Algorithm \ref{alg:computethinset} to find a spanning tree in
each connected component of $H$ with thinness
$\tfrac{6\sqrt{\genus}\alpha}{k}$ for $\alpha =4+\lfloor
2\log_2{(\genus+\frac{3}{2})}\rfloor.$ By the matroid property of
spanning trees one can extend this collection of spanning trees to a
spanning tree of $G$ by adding a set $F \subset E(G)$ of size at
most  $2\sqrt{\genus}$. Since $G$ is $k$-edge connected the thinness
 increases by at most $2\sqrt{\genus}/k$. Therefore since $\alpha \geq 5$, the resulting
tree is
$\tfrac{7\sqrt{\genus}\alpha}{k}=\tfrac{O(\sqrt{\genus}\log{\genus})}{k}$
thin.
\end{proof}

An equivalent way to state above theorem is that for every
orientable surface $\Sigma$, there exists a function $f_\Sigma$ such
that, for any $\epsilon >0$, every $f_\Sigma(\epsilon)$-edge
connected graph $G$ embedded in $S$ has an $\epsilon$-thin spanning
tree. This can be considered as a partial result for the following
conjecture of Goddyn \cite{goddyn:thintreeconj}.

\begin{conjecture}[Goddyn \cite{goddyn:thintreeconj}]
\label{conj:thintreeconj} There exists a function $f(\epsilon)$ such
that, for any $0 < \epsilon < 1$, every $f(\epsilon)$-edge connected
graph  has an $\epsilon$-thin spanning tree.
\end{conjecture}



Goddyn's conjecture is intimately related to  the asymmetric
traveling salesman problem and the integrality gap of  Held-Karp
relaxation. This is established by Asadpour et al. \cite{atsploglogn}
through the following theorem:

\begin{theorem}[Asadpour et al. \cite{atsploglogn}]
\label{thm:circulation} Assume  that we are given an
$(\alpha,s)$-thin spanning tree $T$ with respect to the LP solution
$\bx$ of cost $c(\bx)\leq C\times\HK$. Then we can find a
Hamiltonian cycle of cost no more than $(2\alpha + s)
c(\bx)=C(2\alpha+s) \HK$ in polynomial time.
\end{theorem}

The above theorem relies on a stronger notion of thinness which takes into consideration the costs of edges.
Proposition \ref{thm:thintreegetridofcost} makes this connection more concrete.


\begin{proposition}
\label{thm:thintreegetridofcost} Suppose there exists a
non-decreasing function $g(k)$ such that every $k$-edge connected
graph contains a $\frac{g(k)}{k}$-thin spanning tree. Then any {\em
weighted} $k$-edge connected graph contains a $(\frac{2g(k)}{k},
\frac{2g(k)}{k})$-thin spanning tree.
\end{proposition}
\begin{proof}
Let $G_0$ be a weighed $k$-edge connected graph with cost function $c(e)$ for each edge $e$. Select a $\frac{g(k)}{k}$-thin spanning tree $T_0$, in $G_0$, and remove its edges. Call this new graph $G_1$. Note that each cut $(U,\overline{U})$ of $G_0$ will lose at most $\frac{g(k)}{k}|G_0(U,\overline{U})|$ of its edges. As the size of the minimum cut in $G_0$ is $k$, $G_1$ will be $(k-g(k))$-edge connected.

Similarly, find a $$\frac{g(k-g(k))}{k-g(k)} \leq \frac{g(k)}{k-g(k)}$$ thin spanning tree $T_1$ in $G_1$. The inequality holds by the monotonicity assumption on $g(k)$. Remove the edges of $T_1$ to obtain a $(k-2g(k))$-edge connected graph $G_2$..
Repeat this algorithm on $G_2$ to obtain $k/2g(k)$ spanning trees $T_0,\ldots,T_ {k/2g(k)-1}$, where for each $i$, $T_i$ is a $\frac{g(k)}{k-i g(k)}$-thin spanning tree of the $(k-ig(k))$-edge connected graph $G_i$.

Because  $G_i$ is a spanning subgraph of $G_0$, any spanning thin tree of $G_i$ will be spanning and thin in $G_0$. Moreover, since $0\leq i \leq k/2g(k)-1$ and
$$\frac{g(k)}{k-i g(k)} \leq \frac{2g(k)}{k},$$
each $T_i$ is a $\frac{2g(k)}{k}$-thin spanning tree in $G_0$.
Among the selected trees find the one with the smallest cost. Let $T_j$ be that tree. We have
$$\frac{k}{2g(k)} c(T_j) \leq \sum_{i=0}^{k/2g(k)-1} c(T_i) \leq c(G_0).$$
Thus $T_j$ is a $(\frac{2g(k)}{k}, \frac{2g(k)}{k})$-thin spanning tree of $G_0$.

\end{proof}


%

In the proof of Theorem \ref{thm:constantthintree} we give a
polynomial-time algorithm that finds an
$O(\sqrt{\genus}\log{\genus})/k$-thin spanning tree in a $k$-edge
connected graph embedded on an orientable surface with genus
$\genus$. This result plus the above proposition gives a constant
factor approximation algorithm for ATSP when $\genus$ is constant.
The next theorem establishes this claim.


\begin{theorem}
\label{thm:boundedgenusconstantapp} Given a feasible solution $x$ of
the Held-Karp linear program (\ref{atsplp}),  embedded on an
orientable surface with genus $\genus$,  there is a polynomial-time
algorithm that finds a hamiltonian cycle with a cost that is within
an $O(\sqrt{\genus}\log{\genus})$ of the cost of $x$. In particular,
the approximation factor of the algorithm is at most
$22.5(1+\frac{1}{n})$ when the underlying graph is planar.
\end{theorem}



\begin{proof} %{\bf [Theorem \ref{thm:boundedgenusconstantapp}]}
Let $x$ be a feasible solution of LP (\ref{atsplp})  that can be
embedded on a surface  with genus $\genus$. Construct an undirected
version of $x$ by defining $y_{\{i,j\}} = x_{ij} + x_{ji}$. Define a
new cost function $c'(\{u,v\}) = \min\{c(u,v), c(v,u)\}.$



Round down the fractions in $y$ to the nearest multiple of $1/n^3$.
Construct the integral weighted graph $H$ by adding $n^3
y_{\{i,j\}}$ parallel edges between every pair $i$ and $j$. Since
the size of the support of $y$  is less than $n^2$, we may loose at
most $\frac{1}{n^3}n^2=\frac{1}{n}$ fractions while we are rounding
down the edge fractions and therefore $H$ is
$n^3(2-\frac{1}{n})$-edge connected.



Theorem \ref{thm:constantthintree}  finds a
$\frac{\beta}{n^3(2-\frac{1}{n})}$-thin spanning tree  in $H$, for
$\beta=7\sqrt{\genus}\alpha$ if $\genus>0$ and $\beta=10$ if $H$ is
planar. Use Proposition \ref{thm:thintreegetridofcost} to compute a
$(\frac{2\beta}{n^3(2-\frac{1}{n})},\frac{2\beta}{n^3(2-\frac{1}{n})})$-thin
tree $T$ in $H$ with respect to cost function $c'$. It is easy to
see that it is possible to orient the edges of $T$ into $T^*$ such
that $c'(T) = c(T^*)$. Since the size of each cut of $H$ is at most $n^3$ times of that  of $x$ and $c(H)\leq n^3c(y)\leq n^3c(x)$, $T^*$ is $(\frac{2\beta}{(2-\frac{1}{n})},\frac{2\beta}{(2-\frac{1}{n})})$-thin with respect to $x$. Therefore, using Theorem
\ref{thm:circulation}, we can find a Hamiltonian cycle of cost no
more than

$$\left(2\frac{2\beta}{2-\frac{1}{n}}+\frac{2\beta}{2-\frac{1}{n}}\right) c(x)\leq 3\beta(1+\frac{1}{n}) c(x)$$

in polynomial time.

Since $\beta=O(\sqrt{\genus}\log{\genus})$ is only a function of
$\genus$, we have a constant factor approximation for ATSP  when the
genus of the graph obtained by $x$ is bounded by a constant. In
particular if $\genus=0$, the above calculation shows that we have a
$30(1+\frac{1}{n})$-approximation algorithm. A slightly better
optimization of parameters  and a minor change of Algorithm
\ref{alg:computethinset}  leads to a $22.5(1+\frac{1}{n})$.


We should also add that Mohar \cite{mohar:embedding} proves for any
constant $\genus$, there is a  linear  time algorithm that finds an
embedding of a given graph on the orientable surface with genus
$\genus$, if such an embedding  exists. Therefore, the embeddability
condition in the above Theorem can be checked in polynomial time for
any constant $\genus$.
\end{proof}

%

\begin{remark}
It is worth noting that the genus of an extreme point solution of
Held-Karp relaxation instance with $n$ vertices can be as large as
$\Omega(n)$. In fact, for any odd $r$, it is possible to construct an
extreme point on $r^2$ vertices  that has $K_r$ as a minor. Such an
extreme point can be obtained by the same construction as Carr  and
Vempala \cite[Theorem 3.5]{vempala:4/3integralitygap}  applied to
$K_r$.
\end{remark}


An argument similar to the proof of Theorem
\ref{thm:boundedgenusconstantapp} shows that Goddyn's conjecture
implies constant integrality gap of the Held-Karp relaxation of
ATSP. Furthermore, an algorithmic proof of Goddyn's conjecture
implies a constant factor approximation algorithm for ATSP.


\begin{corollary}
\label{cor:goddynconstintegatsp} If Goddyn's conjecture is true for
some function $f(\epsilon) = O(1/\epsilon)$, then the integrality
gap of Held-Karp relaxation is bounded from above by a constant.
\end{corollary}


\subsection{Nowhere-zero flows and Jaeger's conjecture}
\label{sec:goddyn}

Goddyn's conjecture was inspired by the study of nowhere-zero flows
and in particular in attempting Jaeger's
conjecture~\cite{jaeger:flowconj}. Here, we just state the Jaeger's
conjecture  and refer the reader to Seymour
\cite{seymour:handbookcombinatorics} for more information.


\begin{conjecture}[Jaeger \cite{jaeger:flowconj}]
\label{conj:circularflow} If $G$ is $4k$-edge connected, then for
some orientation of $G$, every subset $S \subset V(G)$ satisfies
$$(k-1) |\delta^-(S)| \leq k |\delta^+(S)| \leq (k+1) |\delta^-(S)|.$$
\end{conjecture}



Jaeger's conjecture has not been proved for any positive integer
$k$ yet. For $k=1$, this is Tutte's 3-flow conjecture and is proved only
for planar graphs. Goddyn's conjecture implies a weaker version of
Jaeger's conjecture in which $4k$ is replaced by an arbitrary
function of $k$ (i.e. $f(\frac{1}{2k+1})$). Even this version is
still open \cite{goddyn:largegirth}.
%
%
%{Goddyn's conjecture in its strong form $f(\epsilon) =
%\frac{2}{\epsilon} - 2$, implies the notoriously difficult Jaeger's
%conjecture  on the existence of nowhere-zero flows. By Proposition
%\ref{thm:thintreegetridofcost} any counter example showing that the
%integrality gap of ATSP is above $6$, yields a counter example for
%Goddyn's conjecture in its strong form.}


Previously, Zhang \cite{zhang:jaeger}  proved Jaeger's conjecture on
graphs with bounded genus. The dependence of his result on the genus
of the graph is pretty much similar to ours: he proves Jaeger's
conjecture for graphs with connectivity
%$(2k-1)\frac{\sqrt{48\genus+47}}{2}$
$O(\sqrt{\genus}k)$ embedded on a surface with genus $\genus$. Since
Goddyn's conjecture implies Jaeger's conjecture with the same
parameters, our result can be seen as a strengthening of
\cite{zhang:jaeger}. On the other hand, the result of
\cite{zhang:jaeger} is based on a vertex splitting argument that
needs  extensive case analysis. It seems that our approach for
proving the stronger result has also lead to a much simpler proof.

{\bf Acknowledgements.}  The authors would like to thank Arash
Asadpour, Luis Goddyn, Michel Goemans, Sergey Norin, Dana Randall,
David Shmoys, Prasad Tetali, and Jan Vondrak for discussions and
comments on an earlier version of this paper.

\bibliographystyle{abbrv}
\bibliography{references}

\end{document}

bg-18.bbl
\begin{thebibliography}{10}

\bibitem{aroraeuclidean}
S.~Arora.
\newblock Polynomial time approximation schemes for euclidean traveling
  salesman and other geometric problems.
\newblock In {\em Journal of the ACM}, pages 2--11, 1996.

\bibitem{Arora:planartsp}
S.~Arora, M.~Grigni, D.~Karger, P.~Klein, and A.~Woloszyn.
\newblock A polynomial-time approximation scheme for weighted planar graph tsp.
\newblock In {\em SODA '98: Proceedings of the ninth annual ACM-SIAM symposium
  on Discrete algorithms}, pages 33--41, Philadelphia, PA, USA, 1998. Society
  for Industrial and Applied Mathematics.

\bibitem{atsploglogn}
A.~Asadpour, M.~X. Goemans, A.~Madry, S.~Oveis~Gharan, and A.~Saberi.
\newblock O(logn/loglogn) approximation to the asymmetric traveling salesman
  problem.
\newblock {\em to appear in SODA 2010}, 2010.

\bibitem{Blaser02}
M.~{Bl\"aser}.
\newblock A new approximation algorithm for the asymmetric {TSP} with triangle
  inequality.
\newblock In {\em SODA}, pages 638--645, 2002.

\bibitem{vempala:4/3integralitygap}
R.~D. Carr and S.~Vempala.
\newblock Towards a 4/3 approximation for the asymmetric traveling salesman
  problem.
\newblock In {\em SODA '00: Proceedings of the eleventh annual ACM-SIAM
  symposium on Discrete algorithms}, pages 116--125, Philadelphia, PA, USA,
  2000. Society for Industrial and Applied Mathematics.

\bibitem{charikar:integralitygap}
M.~Charikar, M.~X. Goemans, and H.~Karloff.
\newblock On the integrality ratio for the asymmetric traveling salesman
  problem.
\newblock {\em Math. Oper. Res.}, 31(2):245--252, 2006.

\bibitem{Demaine:boundedgenus}
E.~D. Demaine, M.~Hajiaghayi, and B.~Mohar.
\newblock Approximation algorithms via contraction decomposition.
\newblock In {\em SODA '07: Proceedings of the eighteenth annual ACM-SIAM
  symposium on Discrete algorithms}, pages 278--287, Philadelphia, PA, USA,
  2007. Society for Industrial and Applied Mathematics.

\bibitem{FeigeS07}
U.~Feige and M.~Singh.
\newblock Improved approximation ratios for traveling salesman tours and path
  sin directed graphs.
\newblock In {\em APPROX}, pages 104--118, 2007.

\bibitem{atsplogn}
A.~M. Frieze, G.~Galbiati, and F.~Maffioli.
\newblock On the worst-case performance of some algorithms for the asymmetric
  traveling salesman problem.
\newblock {\em Networks}, 12:23--39, 1982.

\bibitem{goddyn:thintreeconj}
L.~A. Goddyn.
\newblock Some open problems i like.
\newblock available at
  {\url{http://www.math.sfu.ca/~goddyn/Problems/problems.html}}.

\bibitem{goddyn:largegirth}
L.~A. Goddyn, P.~Hell, A.~Galluccio, and A.~Galluccio.
\newblock High girth graphs avoiding a minor are nearly bipartite.
\newblock {\em J. Comb. Theory (B)}, 83:1--14, 1999.

\bibitem{goemans06}
M.~X. Goemans.
\newblock Minimum bounded degree spanning trees.
\newblock In {\em FOCS}, pages 273--282, 2006.

\bibitem{Papadimitriou:planartsp}
M.~Grigni, E.~Koutsoupias, and C.~Papadimitriou.
\newblock An approximation scheme for planar graph tsp.
\newblock In {\em FOCS '95: Proceedings of the 36th Annual Symposium on
  Foundations of Computer Science}, page 640, Washington, DC, USA, 1995. IEEE
  Computer Society.

\bibitem{Kaplan05}
N.~S. H.~Kaplan, M.~Lewenstein and M.~Sviridenko.
\newblock Approximation algorithms for asymmetric {TSP} by decomposing directed
  regular multigraphs.
\newblock {\em J. {ACM}}, pages 602--626, 2005.

\bibitem{HeldKarp70}
M.~Held and R.~Karp.
\newblock The traveling salesman problem and minimum spanning trees.
\newblock {\em Operations Research}, 18:1138--1162, 1970.

\bibitem{jaeger:flowconj}
F.~Jaeger.
\newblock On circular flows in graphs, finite and infinite sets.
\newblock {\em Colloquia Mathematica Societatis Janos Bolyai 37}, pages
  391--402, 1984.

\bibitem{kleintsp}
P.~N. Klein.
\newblock A linear-time approximation scheme for planar weighted tsp.
\newblock In {\em FOCS '05: Proceedings of the 46th Annual IEEE Symposium on
  Foundations of Computer Science}, pages 647--657, Washington, DC, USA, 2005.
  IEEE Computer Society.

\bibitem{mohar:embedding}
B.~Mohar.
\newblock Embedding graphs in an arbitrary surface in linear time.
\newblock In {\em STOC '96: Proceedings of the twenty-eighth annual ACM
  symposium on Theory of computing}, pages 392--397, New York, NY, USA, 1996.
  ACM.

\bibitem{moharthomassen}
B.~Mohar and C.~Thomassen.
\newblock {\em Graphs on Surfaces}.
\newblock Johns Hopkins University Press, Baltimore, 2001.

\bibitem{seymour:handbookcombinatorics}
P.~D. Seymour.
\newblock Nowhere zero flows.
\newblock In R.~L. Graham, M.~Gr\"{o}tschel, and L.~Lov\'{a}sz, editors, {\em
  Handbook of combinatorics}, volume~1. MIT Press, Cambridge, MA, USA, 1995.

\bibitem{whitney:planargraphs}
H.~Whitney.
\newblock Non-separable and planar graphs.
\newblock {\em Trans. Amer. Math. Soc}, 34(2):339--362, 1932.

\bibitem{zhang:jaeger}
C.~Q. Zhang.
\newblock Circular flows of nearly eulerian graphs and vertex-splitting.
\newblock {\em J. Graph Theory}, 40(3):147--161, 2002.

\end{thebibliography}
