The asymmetric traveling salesman path LP has constant integrality ratio

Abstract

We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. If $\rho _{\text {ATSP}}$ and $\rho _{\text {ATSPP}}$ denote the integrality ratios for the asymmetric TSP and its path version, then $\rho _{\text {ATSPP}}\le 4\rho _{\text {ATSP}}-3$. We prove an even better bound for node-weighted instances: if the integrality ratio for ATSP on node-weighted instances is $\rho _{\text {ATSP}}^{\text{ N }W}$, then the integrality ratio for ATSPP on node-weighted instances is at most $2\rho _{\text {ATSP}}^{\text{ N }W}-1$. Moreover, we show that for ATSP node-weighted instances and unweighted digraph instances are almost equivalent. From this we deduce a lower bound of 2 on the integrality ratio of unweighted digraph instances.

1 Introduction

In the asymmetric traveling salesman path problem (ATSPP), we are given a directed graph $G=(V,E)$, two vertices $s,t\in V$, and weights $c:E\rightarrow {\mathbb {R}}_{\ge 0}\cup \{\infty \}$. We look for a sequence $s=v_0,v_1,\ldots ,v_k=t$ that contains every vertex at least once (an s-t-tour); the goal is to minimize $\sum _{i=1}^k c(v_{i-1},v_i)$. Equivalently, we can assume that G is complete and the triangle inequality $c(u,v)+c(v,w)\ge c(u,w)$ holds for all $u,v,w\in V$, and require the sequence to contain every vertex exactly once.

The special case $s=t$ is known as the asymmetric traveling salesman problem (ATSP). In a recent breakthrough, Svensson, Tarnawski, and Végh [10] found the first constant-factor approximation algorithm for ATSP, and they also proved that its standard LP relaxation has constant integrality ratio.

Feige and Singh [4] showed that any $\alpha$-approximation algorithm for ATSP implies a $(2\alpha +\varepsilon )$-approximation algorithm for ATSPP (for any $\varepsilon >0$). Hence ATSPP also has a constant-factor approximation algorithm. In this paper we prove a similar relation for the integrality ratios. This answers an open question by Friggstad et al. [5].

Given that the upper bound on the integrality ratio by Svensson et al. [10] is a large constant that will probably be improved in the future, such a blackbox result seems particulary desirable. Any improved upper bound on the integrality ratio for ATSP then immediately implies a better bound for the path version.

1.1 The linear programming relaxation

The classical linear programming relaxation for ATSPP (for $s\ne t$) is

Here (and henceforth) we write $c(x):=\sum _{e\in E} c(e) x_{e}$, $x(F):=\sum _{e\in F}x_{e}$, $\delta ^+(U):=\{(u,v)\in E: u\in U,\, v\in V{\setminus } U\}$, $\delta ^-(U):=\delta ^+(V{\setminus } U)$, $\delta (U):=\delta ^-(U)\cup \delta ^+(U)$, $\delta ^+(v):=\delta ^+(\{v\})$, and $\delta ^-(v):=\delta ^-(\{v\})$. For an instance ${{\mathcal {I}}}$ we denote by ${\textsc {lp}}_{{{\mathcal {I}}}}$ the value of an optimum solution to (ATSPP LP) and by ${\textsc {opt}}_{{{\mathcal {I}}}}$ the value of an optimum integral solution. If the instance is clear from the context, we will sometimes simply write ${\textsc {lp}}$ and ${\textsc {opt}}$. Note that the integral solutions of (ATSPP LP) are precisely the incidence vectors of multi-digraphs (V, F) that are connected and become Eulerian by adding one edge (t, s). Hence they correspond to walks from s to t that visit all vertices, in other words: s-t-tours.

The integrality ratio of (ATSPP LP), denoted by $\rho _{\text {ATSPP}}$, is the maximal ratio of the cost of an optimum integral solution and an optimum fractional solution; more precisely $\sup _{{{\mathcal {I}}}} \frac{{\textsc {opt}}_{{{\mathcal {I}}}}}{{\textsc {lp}}_{{{\mathcal {I}}}}}$, where the supremum goes over all instances ${{\mathcal {I}}}=(G,c,s,t)$ with $s\ne t$ for which the denominator is nonzero and finite. Nagarajan and Ravi [8] proved that $\rho _{\text {ATSPP}}=O(\sqrt{n})$, where $n=|V|$. This bound was improved to $O(\log n)$ by Friggstad et al. [6] and to $O(\log n/ \log \log n)$ by Friggstad et al. [5]. In this paper we prove that the integrality ratio of (ATSPP LP) is in fact constant.

Let $\rho _{\text {ATSP}}$ denote the integrality ratio of the classical linear programming relaxation for ATSP:

Svensson et al. [10] proved that $\rho _{\text {ATSP}}$ is a constant. By an infinite sequence of instances, Charikar et al. [2] showed that $\rho _{\text {ATSP}}\ge 2$. It is obvious that $\rho _{\text {ATSPP}}\ge \rho _{\text {ATSP}}$: split an arbitrary vertex of an ATSP instance into two copies, one (called s) inheriting the outgoing edges, and one (called t) inheriting the entering edges; add an edge (t, s) of cost zero and with $x_{(t,s)}:=x(\delta ^+(s))-1$. Figure 1 displays a simpler family of examples, due to Friggstad et al. [5], showing that $\rho _{\text {ATSPP}}\ge 2$.

Fig. 1

Example with integrality ratio approaching 2 as the number of vertices increases. Setting $x_e:=\frac{1}{2}$ for all shown edges defines a feasible solution of (ATSPP LP). If the 2k curved edges have cost 1 and the dotted edges have cost 0, we have ${\textsc {lp}}=c(x)=k$, but any s-t-tour costs at least $2k-1$. (In the figure, $k=4$.) Setting $y_U=\frac{1}{2}$ for the vertex sets indicated by the ellipses and $a_v$ as shown in blue defines an optimum solution of (ATSPP DUAL) (color figure online)

1.2 Our results and techniques

Our main result says that $\rho _{\text {ATSPP}}\le 4\rho _{\text {ATSP}}-3$. Together with [10], this implies a constant integrality ratio for (ATSPP LP).

Similarly as Feige and Singh [4], we transform our ATSPP instance to an ATSP instance by adding a feedback path from t to s and work with an integral solution to this ATSP instance. This may use the feedback path several times and hence consist of several s-t-walks in the original instance. We now merge these to a single s-t-walk that contains all vertices. In contrast to Feige and Singh [4], the merging procedure cannot use an optimum s-t-tour, but only an LP solution. Our merging procedure is similar to one step of the approximation algorithm for ATSP by Svensson et al. [10], but our analysis is more involved. The main difficulty is that the reduction of ATSP to so-called “laminarly-weighted” instances used by Svensson et al. [10] does not work for the path version.

In Sect. 3, we describe our merging procedure and obtain a first bound on the cost of our single s-t-walk that contains all vertices. However, this bound still depends on the difference of two dual LP variables corresponding to the vertices s and t. In Sect. 5 we give a tight upper bound on this value, which will imply our main result $\rho _{\text {ATSPP}}\le 4\rho _{\text {ATSP}}-3$.

The main lemma that we use to prove this bound essentially says that adding an edge (t, s) of cost equal to the LP value does not change the value of an optimum LP solution. Note that using the new edge (t, s) with value one or more is obviously pointless, but it is not obvious that this edge will not be used at all.

For node-weighted instances we obtain a better result: if the integrality ratio for ATSP on node-weighted instances is $\rho _{\text {ATSP}}^{\text{ N }W}$, then the integrality ratio for ATSPP on node-weighted instances is at most $2\rho _{\text {ATSP}}^{\text{ N }W}-1$. Svensson [9] showed that $\rho _{\text {ATSP}}^{\text{ N }W}\le 13$.

Boyd and Elliott-Magwood [1] describe a family of node-weighted instances that shows $\rho _{\text {ATSP}}^{\text{ N }W}\ge 2$. In Sect. 6 we observe that for ATSP node-weighted instances behave in the same way as unweighted instances. Hence for ATSP there is a family of unweighted digraphs whose integrality ratio tends to 2. Therefore such a family exists also for ATSPP.

2 Preliminaries

Given an instance (G, c, s, t) and an optimum solution $x^*$ to (ATSPP LP), we may assume that $G=(V,E)$ is the support graph of $x^*$; so $x^*_{e}>0$ for all $e\in E$. (This is because omitting edges e with $x^*_e=0$ does not change the optimum LP value and can only increase the cost of an optimum integral solution.) We consider the dual LP of (ATSPP LP):

The support of y is the set of nonempty subsets U of $V{\setminus }\{s,t\}$ for which $y_U>0$. We denote it by $\text {supp}(y)$. We say that a dual solution (a, y) has laminar support if for any two nonempty sets $A,B\in \text {supp}(y)$ we have $A\cap B=\emptyset$, $A\subseteq B$, or $B\subseteq A$. See Fig. 1 for an example. We recall some well-known properties of primal and dual LP solutions (cf. Svensson et al. [10]) and sketch proofs for sake of completeness:

Proposition 1

Let (a, y) be an optimum solution to (ATSPP DUAL). Then there is a vector $y'$ such that $(a, y')$ is an optimum solution to (ATSPP DUAL) and has laminar support.

Proof

Among all $y'$ such that $(a,y')$ is an optimum dual solution, choose $y'$ so that $\sum _{U}y'_U|U|$ is minimum. Then $(a,y')$ has laminar support: suppose $y'_A>0$ and $y'_B>0$ and $A\cap B,A{\setminus } B,B{\setminus } A\not =\emptyset$, then we could decrease $y'_A$ and $y'_B$ and increase $y'_{A{\setminus } B}$ and $y'_{B{\setminus } A}$ while maintaining dual feasibility. $\square$

Proposition 2

Let (G, c, s, t) be an instance of ATSPP, where G is the support graph of an optimum solution $x^*$ to (ATSPP LP). Let (a, y) be an optimum solution of (ATSPP DUAL). Let $U\in \{V\}\cup supp (y)$. Then the strongly connected components of G[U] can be numbered $U_1,\ldots ,U_l$ such that $\delta ^-(U)=\delta ^-(U_1)$, $\delta ^+(U)=\delta ^+(U_l)$, and $\delta ^+(U_i)=\delta ^-(U_{i+1})\ne \emptyset$ for $i=1,\ldots ,l-1$. If $U=V$, then $s\in U_1$ and $t\in U_l$.

Proof

By complementary slackness, $y_U>0$ implies $x^*(\delta (U))=2$ and hence $x^*(\delta ^-(U))=1$. We first prove the statement of the Proposition for every set $\emptyset \ne U \subseteq V{\setminus }\{s\}$ with $x^*(\delta ^-(U))=1$. Let $U_1,\ldots ,U_l$ be a topological order of the strongly connected components of G[U].

We now use induction on l. For $l=1$, the statement is trivial. Now assume $l>1$. Since $s\notin U$, we have $1 \le x^*(\delta ^-(U_1)) \le x^*(\delta ^-(U)) =1$. Thus, $\delta ^-(U_1) = \delta ^-(U)$. This implies $\delta ^-(U{\setminus } U_1) \subseteq \delta ^+(U_1)$. Using again $s\notin U$, we have $x^*(\delta ^+(U_1)) \le x^*(\delta ^-(U_1))=1 \le x^*(\delta ^-(U{\setminus } U_1))$. Thus, we have $\delta ^-(U{\setminus } U_1) =\delta ^+(U_1)$ and $x^*(\delta ^-(U{\setminus } U_1))=1$. Hence, applying the induction hypothesis to $U{\setminus } U_1$ completes the proof for U.

It remains to consider the case $U=V$. Let $U_1,\ldots ,U_l$ be again a topological order of the strongly connected components of $G[U]=G$. Then $s\in U_1$ and $t\in U_l$ because for every vertex v in G, v is reachable from s, and t is reachable from v. If $l=1$, we are done. Now assume $l>1$. We have $\delta ^-(U{\setminus } U_1) = \delta ^+(U_1)$. Because $s\in U_1$ and $t\notin U_1$, we have $x^*(\delta ^-(U{\setminus } U_1))=x^*(\delta ^+(U_1)) =1$. Since we already proved the assertion for $U{\setminus } U_1$, the proof is complete. $\square$

Proposition 3

Let (G, c, s, t) be an instance of ATSPP, where G is the support graph of an optimum solution to (ATSPP LP). Let (a, y) be an optimum solution to (ATSPP DUAL) with laminar support. Let ${{\bar{U}}}\in \{V\}\cup supp (y)$ and $v,w\in {{\bar{U}}}$. If w is reachable from v in the induced subgraph $G[{{\bar{U}}}]$, then there is a v-w-path in $G[{{\bar{U}}}]$ that enters and leaves every set $U\in \text {supp}(y)$ at most once.

Proof

Let P be a path from v to w in $G[{{\bar{U}}}]$. Repeat the following. Let U be a maximal set with $y_U>0$ that P enters or leaves more than once. If P enters U more than once, let $v'$ be the vertex after entering the first time and $w'$ the vertex after entering the last time. By Proposition 2, $v'$ and $w'$ are in the same strongly connected component of G[U] (the first one in the topological order). We replace the $v'$-$w'$-subpath of P by a path in G[U]. Proceed analogously if P leaves U more than once. $\square$

3 Bounding the integrality ratio

We first transform an instance and a solution to (ATSPP LP) to an instance and a solution to (ATSP LP) and work with an integral solution of this ATSP instance. The following lemma is essentially due to Feige and Singh [4]. For completeness, we prove it here again for our setting.

Lemma 1

Let $d\ge 0$ be a constant. Then $\rho _{\text {ATSPP}}\le (d+1)\rho _{\text {ATSP}}-d$ if the following condition holds for every instance ${{\mathcal {I}}}=(G,c,s,t)$ of ATSPP where G is the support graph of an optimum solution to (ATSPP LP): If there are two s-t-walks $P_1$ and $P_2$ of total cost L in G, there is a single s-t-walk P in G with cost $c(P)\le L+d\cdot {\textsc {lp}}$ which contains all vertices of $P_1$ and $P_2$.

Proof

Let ${{\mathcal {I}}}=(G,c,s,t)$ be an instance of ATSPP and $x^*$ be an optimum solution to (ATSPP LP) such that G is the support graph of $x^*$. Then ${\textsc {lp}}=c(x^*)$. Consider the instance ${{\mathcal {I}}}'=(G', c')$ of ATSP that arises from ${{\mathcal {I}}}$ as follows. We add a new vertex v to G and two edges (t, v) and (v, s) with weights $c'(t,v) =d\cdot {\textsc {lp}}$ and $c'(v,s)= 0$. Then there is a feasible solution of (ATSP LP) for ${{\mathcal {I}}}'$ with cost $(d+1)\cdot {\textsc {lp}}$ (extend $x^*$ by setting $x^*_{(t,v)}=x^*_{(v,s)}=1$). Hence there is a solution to ATSP for ${{\mathcal {I}}}'$ with cost at most $(d+1)\rho _{\text {ATSP}}\cdot {\textsc {lp}}$. Let R be such a solution. Then R has to use (t, v) and (v, s) at least once, since it has to visit v. By deleting all copies of (t, v) and (v, s) from R, we get $k>0$s-t-walks in G with total cost at most $(d+1)\rho _{\text {ATSP}}\cdot {\textsc {lp}}-dk\cdot {\textsc {lp}}$ such that every vertex of G is visited by at least one of them. As long as $k > 1$, by our assumption we can replace two of the s-t-walks by a single one, increasing the cost by at most $d\cdot {\textsc {lp}}$ and decreasing k by one. We end up with a single s-t-walk P with cost $c(P)\le (d+1)\rho _{\text {ATSP}}\cdot {\textsc {lp}}-d\cdot {\textsc {lp}}$ in G, which contains every vertex of G. This walk is a solution of ATSPP for ${{\mathcal {I}}}$ and thus we have $\rho _{\text {ATSPP}}\le (d+1)\rho _{\text {ATSP}}-d$ as proposed. $\square$

The following procedure is similar to one step (“inducing on a tight set”) of the approximation algorithm for ATSP by Svensson et al. [10].

Lemma 2

Let (G, c, s, t) be an instance of ATSPP, where G is the support graph of an optimum solution to (ATSPP LP). Let (a, y) be an optimum solution to (ATSPP DUAL) with laminar support.

Let $P_1$ and $P_2$ be s-t-walks in G with total cost L. Then there is a single s-t-walk P in G which contains every vertex of $P_1$ and $P_2$ and has cost at most $L+{\textsc {lp}}+2(a_s-a_t)$.

Proof

Let $V_1, \ldots , V_l$ be the vertex sets of the strongly connected components of G in their topological order, which is unique by Proposition 2. Let $P_i^j$ be the section of $P_i$ that visits vertices in $V_j$ (for $i=1,2$ and $j=1, \ldots , l$). By Proposition 2 applied to $U=V$, none of these sections of $P_i$ is empty. (Such a section might consist of a single vertex and no edges, but it has to contain at least one vertex.)

We consider paths $R^j$ in G for $j=1, \ldots , l$ that we will use to connect the walks $P^j_1$ and $P^j_2$ to a single walk visiting all vertices in $V_j$. See Fig. 2. If j is odd, let $R^j$ be a path from the last vertex of $P_1^j$ to the first vertex of $P_{2}^j$. If j is even, let $R^j$ be a path from the last vertex of $P_2^j$ to the first vertex of $P_{1}^j$. (Such paths exists because $G[V_j]$ is strongly connected.) By Proposition 3 we can choose the paths $R^j$ such that they do not enter or leave any element of $\text {supp}(y)$ more than once.

Fig. 2

Construction of P. The s-t-walks $P_1$ and $P_2$ are shown with solid and dotted lines. (Here, $P_1$ is the upper red walk and $P_2$ is shown in blue at the bottom.) The vertex sets $V_1,\ldots , V_l$ of the strongly connected components are indicated by the green ellipses. The red and blue solid edges of the walks $P_i$ that are those that are used in the walk P. The dashed black arrows indicate the paths $R^j$ (color figure online)

We now construct our s-t-walk P that will visit every vertex of $P_1$ and $P_2$. We start by setting $P=s$ and then add for $j=1, \ldots , l$ all the vertices in $V_j$ to P as follows. If j is odd, we append $P_1^j$ and $R^j$ and then $P_2^j$. If j is even, we append $P_2^j$ and $R^j$ and then $P_1^j$. Note that when moving from one connected component $V_j$ to the next component $V_{j+1}$, we use an edge from either $P_1$ (if j is even) or $P_2$ (if j is odd). Then P is, indeed, an s-t walk in G and contains every vertex of $P_1$ and $P_2$. We now bound the cost of the walk P. For every edge $e=(v,w)$ of P we have by complementary slackness

$$\begin{aligned} c(e) \ = \ a_w - a_v + \sum _{U:e\in \delta (U)}y_U. \end{aligned}$$

For an s-t-walk Q in G we have

$$\begin{aligned} c(Q) \ = \sum _{(v,w)\in E(Q)}\left( a_w -a_v +\sum _{U:(v,w)\in \delta (U)}y_U\right) \ = \ a_t - a_s + c^y(Q), \end{aligned}$$

(1)

where the cost function $c^y$ is defined as $c^y(e):= \sum _{U:e\in \delta (U)}y_U$. Hence, to bound the cost of the s-t-walk P, we can bound $c^y(P)$ and then subtract $a_s$ and add $a_t$.

P is constructed from pieces of $P_1$ and $P_2$ and the paths $R^j$. Each of the paths $R^j$ can only contain vertices of $V_j$. Two paths $R^j$ and $R^{j'}$, such that $j\ne j'$, can never both enter or both leave the same element of $\text {supp}(y)$: otherwise they would contain vertices of the same strongly connected component of G by Proposition 2. Thus every element of $\text {supp}(y)$ is entered at most once and left at most once on all the paths $R^j$ used in the construction of P, and the total $c^y$ cost of these paths is at most $\sum _{U}2y_U={\textsc {lp}}+a_s-a_t$. The $c^y$ cost of the edges of $P_1$ and $P_2$ is

$$\begin{aligned} c^y(P_1) + c^y(P_2) \ = \ \left( c(P_1)-a_t+a_s\right) + \left( c(P_2)-a_t+a_s\right) \ = \ L+2\cdot a_s-2 \cdot a_t. \end{aligned}$$

Consequently, we have

$$\begin{aligned} c(P)&\ =\ a_t - a_s + c^y(P) \\&\ \le \ a_t - a_s + L+2\cdot a_s-2 \cdot a_t+ \bigl ( {\textsc {lp}}+a_s-a_t \bigr ) \\&\ = \ L+{\textsc {lp}}+2(a_s-a_t) \end{aligned}$$

as claimed. $\square$

Svensson et al. [10] reduced ATSP to so-called laminarly-weighted instances. In a laminarly-weighted instance we have $a=0$ (and (a, y) has laminar support). For such instances Lemmas 1 and 2 would immediately imply our main result (even with better constants). However, the reduction to laminarly-weighted instances for ATSP does not yield an analogous statement for the path version. Instead, we will prove that $a_s-a_t\le {\textsc {lp}}$ for some optimum dual LP solution (Sect. 5).

Let us first consider a simpler special case.

4 The integrality ratio for node-weighted instances

Definition 1

An instance (G, c, s, t) of ATSPP or an instance (G, c) of ATSP is called node-weighted if there are nonnegative node weights $(c_v)_{v\in V}$ such that $c(v,w)=c_v+c_w$ for every edge (v, w).

Note that node-weighted instances are not necessarily symmetric because it might happen that an edge (v, w) exists, but (w, v) does not exist. Since $x(\delta (s)) \ge 1$, $x(\delta (t))\ge 1$ and $x(\delta (v)) \ge 2$ for $v\notin \{s,t\}$ for every LP solution x, we have ${\textsc {lp}}\ge c_s + c_t + \sum _{v\in V{\setminus } \{s,t\}}2c_v$.

Theorem 1

Let $\rho _{\text {ATSP}}^{\text {NW}}$ be the integrality ratio for ATSP on node-weighted instances and $\rho _{\text {ATSPP}}^{\text {NW}}$ be the integrality ratio for ATSPP on node-weighted instances. Then

$$\begin{aligned} \rho _{\text {ATSPP}}^{\text {NW}}\ \le \ 2 \rho _{\text {ATSP}}^{\text {NW}}-1. \end{aligned}$$

Proof

First we show how to modify the proof of Lemma 1 for node-weighted instances and $d=1$. For a node-weighted instance ${{\mathcal {I}}}=(G,c)$, let ${{\mathcal {I}}}'=(G',c')$ result from ${{\mathcal {I}}}$ by adding a vertex v with weight $c_v=\frac{1}{2}({\textsc {lp}}-c_s-c_t)$ and two edges (t, v) and (v, s). Note that ${\textsc {lp}}\ge c_s+c_t$ and hence $c_v\ge 0$. Then continuing with the node-weighted instance ${{\mathcal {I}}}'$ as in the proof of Lemma 1 yields the following: it suffices to show that for node-weighted instances of ATSPP, we can merge any two s-t-walks to a single s-t-walk P as in Lemma 2, but with $c(P)\le L+{\textsc {lp}}$.

We construct P as in the proof of Lemma 2. Again we first bound the cost of the paths $R^j$. For $1\le j\le l$ each vertex in $V_j$ can only be contained in the path $R^j$ (and not in a path $R^{j'}$ for $j' \ne j$). Hence every vertex can be used in at most one path $R^j$. Furthermore, the vertices s and t are only used as the last or first vertices of paths $R^j$. Hence the total cost of all paths $R^j$ can be bounded from above by

$$\begin{aligned} c_s+c_t +\sum _{v\in V\backslash \{s,t\}}2c_v \ \le \ {\textsc {lp}}. \end{aligned}$$

This shows $c(P)\le L+{\textsc {lp}}$ and completes the proof. $\square$

Since Svensson [9] showed $\rho _{\text {ATSP}}^{\text {NW}}\le 13$, this implies $\rho _{\text {ATSPP}}^{\text {NW}}\le 25$.

5 Bounding the difference of $a_s$ and $a_t$

The goal of this section is to bound the difference of the dual variables $a_s$ and $a_t$ by ${\textsc {lp}}$. Using Lemmas 1 and 2, this will imply our main result $\rho _{\text {ATSPP}}\le 4\rho _{\text {ATSP}}-3$.

Fig. 3

Example of an instance with ${\textsc {lp}}=0$ and an optimum dual solution with $a_s-a_t =2$. The blue numbers below the vertices show the dual variables $a_s=1$, $a_v=0$ and $a_t = -1$. Of course, this instance has a different optimum dual solution in which all variables are zero (color figure online)

Figure 3 shows that we cannot bound $a_s - a_t$ by ${\textsc {lp}}$ for an arbitrary optimum dual solution (a, y). Thus, we will now work with an optimum dual solution (a, y) with $a_s-a_t$ minimum. Note that this minimum is attained because for every feasible dual solution (a, y) we have $a_s-a_t\ge -{\textsc {lp}}$.

First, we give an equivalent characterization of the minimum value of $a_s-a_t$ in any optimum dual solution. This will not be needed to prove our main result, but might help to get some intuition.

Lemma 3

Let ${{\mathcal {I}}}= (G,c,s,t)$ be an instance of ATSPP and let $\varDelta \ge 0$. Now consider the instance ${{\mathcal {I}}}' = (G+e',c,s,t)$, where we add an edge $e'=(t,s)$ with $c(e'):= \varDelta$. Then ${\textsc {lp}}_{{{\mathcal {I}}}} \ge {\textsc {lp}}_{{{\mathcal {I}}}'}$. Moreover, ${\textsc {lp}}_{{{\mathcal {I}}}} = {\textsc {lp}}_{{{\mathcal {I}}}'}$ if and only if there exists an optimum solution (a, y) of (ATSPP DUAL) for the instance ${{\mathcal {I}}}$ with $a_s - a_t \le \varDelta$.

Proof

Every feasible solution x of (ATSPP LP) for ${{\mathcal {I}}}$ can be extended to a feasible solution of (ATSPP LP) for ${{\mathcal {I}}}'$ by setting $x_{e'}:=0$. This shows ${\textsc {lp}}_{{{\mathcal {I}}}} \ge {\textsc {lp}}_{{{\mathcal {I}}}'}$.

The dual LPs for the two instances are identical, except for the constraint corresponding to $e'$, which is

$$\begin{aligned} \varDelta \ = \ c(e') \ \ge \ a_s - a_t + \sum _{\emptyset \ne U\subseteq V{\setminus }\{s,t\}, e'\in \delta (U)} y_U \ = \ a_s -a_t. \end{aligned}$$

(2)

Suppose ${\textsc {lp}}_{{{\mathcal {I}}}} = {\textsc {lp}}_{{{\mathcal {I}}}'}$. Let (a, y) be an optimum dual solution for ${{\mathcal {I}}}'$. Then, (2) is satisfied and (a, y) is also feasible for the dual LP for the instance ${{\mathcal {I}}}$. Moreover, since ${\textsc {lp}}_{{{\mathcal {I}}}} = {\textsc {lp}}_{{{\mathcal {I}}}'}$, the dual solution (a, y) is also optimum for the instance ${{\mathcal {I}}}$.

For the reverse direction, let (a, y) be an optimum solution to (ATSPP DUAL) for the instance ${{\mathcal {I}}}$ with $a_s - a_t \le \varDelta$. Then (a, y) satisfies (2) and thus is also feasible for (ATSPP DUAL) for ${{\mathcal {I}}}'$. Hence, ${\textsc {lp}}_{{{\mathcal {I}}}'} \ge {\textsc {lp}}_{{{\mathcal {I}}}}$. $\square$

For bounding $a_s-a_t$ we will need the following.

Lemma 4

Let (G, c, s, t) be an instance of ATSPP, where G is the support graph of an optimum solution to (ATSPP LP). Let (a, y) be an optimum solution of (ATSPP DUAL) such that $a_s - a_t$ is minimum. Let ${{\bar{U}}}\subseteq V{\setminus }\{s,t\}$ such that every s-t-path in G enters (and leaves) ${{\bar{U}}}$ at least once. Then $y_{{{\bar{U}}}}=0$.

Proof

Suppose $y_{{{\bar{U}}}} >0$ and let $\varepsilon :=y_{{{\bar{U}}}}$. Let R be the set of vertices reachable from s in $G -{{\bar{U}}}$. We define a dual solution $({{\bar{a}}}, {{\bar{y}}})$ as follows:

$$\begin{aligned} {{\bar{y}}} (U) :=&\ {\left\{ \begin{array}{ll} y_U - \varepsilon &{}\quad \text { if }U = {{\bar{U}}} \\ y_U &{}\quad \text { else} \end{array}\right. } \\ {{\bar{a}}}_v :=&\ {\left\{ \begin{array}{ll} a_v - \varepsilon &{}\quad \text { if }v\in R \\ a_v &{}\quad \text { if }v \in {{\bar{U}}} \\ a_v + \varepsilon &{}\quad \text { else}. \end{array}\right. } \end{aligned}$$

Fig. 4

Modifying the dual solution in the proof of Lemma 4. The green and blue numbers in the bottom indicate the change of the dual node variables. In red the decrease of the variable $y_{{{\bar{U}}}}$ is indicated. There is no edge from R to $V{\setminus } (R \cup \bar{U})$ (color figure online)

See Fig. 4. We claim that $(\bar{a}, {{\bar{y}}})$ is an optimum (and feasible) solution to (ATSPP DUAL). Note that $t\in V {\setminus } \left( R \cup {{\bar{U}}}\right)$ and thus ${{\bar{a}}}_t = a_t + \varepsilon$. Since $s\in R$, we have ${{\bar{a}}}_s - {{\bar{a}}}_t < a_s - a_t$. Thus, if $(\bar{a}, {{\bar{y}}})$ is indeed optimum (and feasible), we obtain a contradiction to our choice of the dual solution (a, y).

First, we observe that $({{\bar{a}}}, {{\bar{y}}})$ and (a, y) have the same objective value since

$$\begin{aligned} {{\bar{a}}}_t- {{\bar{a}}}_s + \sum _{\emptyset \ne U \subseteq V{\setminus } \{s,t\}} 2{{\bar{y}}}_U \ =\ \left( a_t + \varepsilon \right) - \left( a_s - \varepsilon \right) +\sum _{\emptyset \ne U \subseteq V{\setminus } \{s,t\}} 2 y_U - 2 \varepsilon . \end{aligned}$$

By our choice of $\varepsilon$, the vector ${{\bar{y}}}$ will be non-negative. Now consider an edge $e=(v,w)\in E(G)$. We need to show that

$$\begin{aligned} {{\bar{a}}}_w - {{\bar{a}}}_v + \sum _{U : e\in \delta (U)} {{\bar{y}}}_U\ \le \ c(e). \end{aligned}$$

(3)

To prove this we will show that

$$\begin{aligned} {{\bar{a}}}_w - a_w - {{\bar{a}}}_v + a_v + \sum _{U : e\in \delta (U)} \left( {{\bar{y}}}_U - y_U\right) \le 0. \end{aligned}$$

(4)

Since (a, y) is a feasible dual solution, this will imply (3). We have

$$\begin{aligned} {{\bar{a}}}_w - a_w :=&\ {\left\{ \begin{array}{ll} - \varepsilon &{}\quad \text { if }w\in R \\ 0 &{}\quad \text { if }w \in {{\bar{U}}} \\ \varepsilon &{}\quad \text { else,} \end{array}\right. } \\ - {{\bar{a}}}_v + {{\bar{a}}}_v :=&\ {\left\{ \begin{array}{ll} \varepsilon &{}\quad \text { if }v\in R \\ 0 &{}\quad \text { if }v \in {{\bar{U}}} \\ -\varepsilon &{}\quad \text { else,} \end{array}\right. } \\ \sum _{U : e\in \delta (U)} \left( {{\bar{y}}}_U - y_U\right) :=&\ {\left\{ \begin{array}{ll} - \varepsilon &{}\quad \text { if }(v,w)\in \delta ({{\bar{U}}}) \\ 0 &{}\quad \text { else}. \end{array}\right. } \end{aligned}$$

Since ${{\bar{a}}}_w - a_w\le \varepsilon$ and ${{\sum }}_{U : e\in \delta (U)} \left( {{\bar{y}}}_U - y_U\right) \le 0$, it suffices to consider the cases $v\in R$ and $v\in {{\bar{U}}}$. If $v\in R$, we have by definition of R, either $w\in R$ or $w\in {{\bar{U}}}$. In both cases (4) holds, because if $w\in {{\bar{U}}}$, we have $(v,w)\in \delta ({{\bar{U}}})$. Now let $v\in \bar{U}$. Then if $(v,w)\in \delta ({{\bar{U}}})$, we have $\sum _{U : e\in \delta (U)} \left( {{\bar{y}}}_U - y_U\right) = -\varepsilon$, implying (4). Otherwise, $w\in {{\bar{U}}}$ and ${{\bar{a}}}_w - a_w- {{\bar{a}}}_v + a_v = 0$.

This shows that $({{\bar{a}}}, {{\bar{y}}})$ is an optimum dual solution and ${{\bar{a}}}_s - {{\bar{a}}}_t < a_s - a_t$, a contradiction. Hence, $y_{\bar{U}}=0$. $\square$

We will need the following variant of Menger’s Theorem.

Lemma 5

Let G be a directed graph and $s,t\in V(G)$ such that t is reachable from s in G. Let $U\subseteq V(G) {\setminus } \{s,t\}$ such that for every vertex $u\in U$, there exists an s-t-path in $G- u$. Then there exist two s-t-paths $P_1$ and $P_2$ in G such that no vertex $u\in U$ is contained in both $P_1$ and $P_2$.

Proof

We construct a graph $G'$ that arises from G as follows. We split every vertex $u\in U$ into two vertices $u^-$ and $u^+$ that are connected by an edge $e_u := (u^-, u^+)$. Every edge (v, u) is replaced by an edge $(v,u^-)$ and every edge (u, v) is replaced by an edge $(u^+,v)$. In the graph $G'$ we now define integral edge capacities. Every edge $e_u$ for $u\in U$ has capacity one. All other edges, i.e. all edges corresponding to edges of G, have infinite capacity.

Since for every vertex $u\in U$ there exists an s-t-path in $G-u$, for every $u\in U$ there exists an s-t-path in $G' - e_u$. Thus, the minimum capacity of an s-t-cut in $G'$ is at least two. Hence, there exists an integral s-t-flow of value two in $G'$ with the defined edge capacities. This flow can be decomposed into two s-t-paths $P_1'$ and $P_2'$ (and possibly cycles). By the choice of the edge capacities no edge $e_u$ for $u\in U$ occurs in both paths. Since this edge $e_u$ is the only outgoing edge of $u^-$ and the only incoming edge of $u^+$, an s-t-path using $u^-$ or $u^+$ must use $e_u$, and at most one of $P_1'$ and $P_2'$ can do so.

Hence, contracting the edges $e_u$ (for $u\in U$) yields two s-t-paths $P_1$ and $P_2$ in G such that no vertex $u\in U$ is contained in both $P_1$ and $P_2$. $\square$

See Fig. 5. We will now continue to work with a dual solution (a, y) that minimizes $a_s -a_t$. By Proposition 1, we can assume in addition that (a, y) has laminar support.

Lemma 6

Let (G, c, s, t) be an instance of ATSPP, where G is the support graph of an optimum solution to (ATSPP LP). Let (a, y) be an optimum solution to (ATSPP DUAL) that has laminar support and minimum $a_s - a_t$.

Then G contains two s-t-paths $P_1$ and $P_2$ such that for every set $U\in \text {supp}(y)$ we have $|E(P_1) \cap \delta (U)| + |E(P_2) \cap \delta (U)| \le 2$.

Proof

By Lemma 4, for every set $U\in \text {supp}(y)$ there is an s-t-path in G that visits no vertex in U. We contract all maximal sets $U\in \text {supp}(y)$. Using Lemma 5, we can find two s-t-paths such that each vertex arising from the contraction of a set $U\in \text {supp}(y)$ is visited by at most one of the two paths.

Now we revert the contraction of the sets $U\in \text {supp}(y)$. We complete the edge sets of the two s-t-paths we found before (which are not necessarily connected anymore after undoing the contraction), to paths $P_1$ and $P_2$ with the desired properties. To see that this is possible, let v be the end vertex of an edge entering a contracted set $U\in \text {supp}(y)$ and let w be the start vertex of an edge leaving U. Then by Proposition 2, the vertex w is reachable from v in G[U]. Let ${{\bar{U}}}$ be the minimal set in $\text {supp}(y)$ that contains both v and w. By Proposition 3, we can choose a v-w-path in $G[{{\bar{U}}}]$ that enters and leaves every set $U'\in \text {supp}(y)$ with $U' \subsetneq {{\bar{U}}}$ at most once. $\square$

We finally show our main lemma.

Fig. 5

The paths $P_1$ and $P_2$ as in Lemma 6. In black the vertex sets $U\in \text {supp}(y)$ are shown. The paths $P_1$ and $P_2$ are not necesarily disjoint but they never both cross the same set U with $y_U>0$

Lemma 7

Let ${{\mathcal {I}}}=(G,c,s,t)$ be an instance of ATSPP, where G is the support graph of an optimum solution to (ATSPP LP). Then there is an optimum solution (a, y) of (ATSPP DUAL) with laminar support and $a_s -a_t \le {\textsc {lp}}$.

Proof

Let (a, y) be an optimum solution to (ATSPP DUAL) that has laminar support and minimum $a_s - a_t$. Note that such an optimum dual solution exists by Proposition 1. We again define the $c^y$ cost of an edge e to be $c^y(e) = \sum _{U: e\in \delta (U)} y_U$. By Lemma 6, G contains two s-t-paths $P_1$ and $P_2$ such that $c^y(P_1) + c^y(P_2) \le \sum _{\emptyset \ne U \subseteq V{\setminus } \{s,t\}} 2\cdot y_U$. Then, using (1),

$$\begin{aligned} 0&\le \ c(P_1) + c(P_2) \\&=\ c^y(P_1) - (a_s - a_t) + c^y(P_2) - (a_s - a_t) \\&\le \ \sum _{\emptyset \ne U \subseteq V{\setminus } \{s,t\}} 2\cdot y_U - 2 (a_s - a_t), \end{aligned}$$

implying

$$\begin{aligned} a_s -a_t \ \le \ \sum _{\emptyset \ne U \subseteq V{\setminus } \{s,t\}} 2\cdot y_U - (a_s - a_t) \ = \ {\textsc {lp}}. \end{aligned}$$

$\square$

Fig. 6

Example with no optimum dual solutions with $a_s-a_t<{\textsc {lp}}$: The numbers next to the arcs denote their cost. For this instance we have ${\textsc {lp}}=1$. However adding an edge (t, s) with cost $\gamma <1$ would result in an instance with ${\textsc {lp}}=\gamma$. By Lemma 3 there cannot be an optimum dual solution where $a_s-a_t<1={\textsc {lp}}$

We remark (although we will not need it) that Lemma 7 also holds for general instances. To adapt the proof, work with the subgraph $G'$ of G that contains all edges of G for which the dual constraint is tight. Now $G'$ plays the role of G in the proof, and by choosing $\varepsilon$ small enough in the proof of Lemma 4 we maintain dual feasibility also for the edges that are not in $G'$.

By Lemma 3, this also shows that adding an edge (t, s) of cost equal to the LP value does not change the value of an optimum LP solution.

The instance in Fig. 6 shows that the bound $a_s-a_t \le {\textsc {lp}}$ is tight. Note that the bound is also tight for the instance in Fig. 1 in which $x^*_e>0$ for all edges e, and in which the integrality ratio is arbitrarily close to the best known lower bound of 2.

We will now prove our main result.

Theorem 2

Let $\rho _{\text {ATSP}}$ be the integrality ratio of (ATSP LP). Then the integrality ratio $\rho _{\text {ATSPP}}$ of (ATSPP LP) is at most $4\rho _{\text {ATSP}}- 3$.

Proof

Let (G, c, s, t) be an instance of ATSPP, where G is the support graph of an optimum solution to (ATSPP LP). By Lemma 7, there is an optimum dual solution (a, y) with laminar support and $a_s-a_t \le {\textsc {lp}}$. Using Lemma 2, this implies that the condition of Lemma 1 is fulfilled for $d=3$. This shows $\rho _{\text {ATSPP}}\le 4\rho _{\text {ATSP}}- 3$. $\square$

6 Node-weighted and unweighted instances

Here we observe that, for ATSP, node-weighted instances are not much more general than unweighted instances. We call an LP solution x minimal if there is no feasible solution $x'\ne x$ with $x'\le x$ componentwise.

Lemma 8

For every minimal solution x of (ATSP LP), we have $x(E(G))\le n^2$, where $n=|V(G)|$.

Proof

Choose an arbitrary root $r\in V$ and let $P=\{y \in {\mathbb {R}}^{E(G)}_{\ge 0}: y(\delta ^-(U))\ge 1 \text { for } \emptyset \not =U\subseteq V{\setminus }\{r\}\}$. A vector is feasible for (ATSP LP) if and only if it is a circulation that belongs to P. Let $y\le x$ be a minimal vector in P. The minimal vectors in P are the convex combinations of incidence vectors of spanning arborescences rooted at r (Edmonds [3]); hence $y(E(G))=n-1$. There are cycles $C_j$ and edge sets $S_j \subseteq C_j$ ($j=1,\ldots ,l$) such that $x=\sum _{j=1}^l \lambda _j \chi ^{C_j}$ and $y= \sum _{j=1}^l \lambda _j \chi ^{S_j}$ for some positive coefficients $\lambda _j$. Note that none of the sets $S_j$ can be empty because otherwise $x'= x - \lambda _j \chi ^{C_j}$ would be a circulation that belongs to P, contradicting the minimality of x. We conclude $x(E(G)) = \sum _{j=1}^l \lambda _j |C_j| \le \sum _{j=1}^l \lambda _j \cdot n |S_j| = n \cdot y(E(G)) = n(n-1)$. $\square$

Lemma 9

Let $\varepsilon >0$. Let (G, c) be a node-weighted instance of ATSP with n vertices. Then we can find in polynomial time a constant $M>0$ and an unweighted digraph $G'$ with $O(\frac{n^2}{\varepsilon })$ vertices such that

• (i) ${\textsc {lp}}_{(G,c)} \le M \cdot {\textsc {lp}}_{G'} \le (1+\varepsilon ) {\textsc {lp}}_{(G,c)}$,

• (ii) ${\textsc {opt}}_{(G,c)} \le M \cdot {\textsc {opt}}_{G'} \le (1+\varepsilon ) {\textsc {opt}}_{(G,c)}$, and

• (iii) for every tour $F'$ in the unweighted digraph $G'$ there is a corresponding tour F in G such that $c(F) \le M |F'|$ and F can be obtained from $F'$ in polynomial time.

Proof

Let $c_v\ge 0$ ($v\in V(G)$) be the node weights, i.e., $c(v,w)=c_v+c_w$ for all $(v,w)\in E$. Let $c(V(G))=\sum _{v\in V(G)} c_v$ denote the sum of all node weights. If $c(V(G))=0$, the instance is trivial, we can choose $G'$ to consist of a single vertex.

Otherwise let $n=|V(G)|$, $M:=\frac{2\varepsilon \cdot c(V(G))}{n^2}$ and ${{\bar{c}}}_v := \lfloor \frac{2c_v}{M}\rfloor$ for all $v\in V(G)$. Replace every vertex v of G with ${{\bar{c}}}_v > 0$ by two vertices $v^-$ and $v^+$, such that $v^-$ inherits the entering edges and $v^+$ inherits the outgoing edges, and add a path $P_v$ of $\bar{c}_v$ edges from $v^-$ to $v^+$. This defines $G'$. Note that $|V(G')| = n + \sum _{v\in V(G)}{{\bar{c}}}_v \le n+\frac{n^2}{\varepsilon }$.

Every solution x to (ATSP LP) for (G, c) corresponds to a solution $x'$ to (ATSP LP) for $G'$, simply by setting $x'_e:=x(\delta ^+(v))$ for all edges e of $P_v$. Then

$$\begin{aligned} x'(E(G')) =&\sum _{v\in V(G)} \left( 1+{{\bar{c}}}_v\right) \, x(\delta ^+(v)) \\ =&\sum _{v\in V(G)} \left( 1+\left\lfloor \frac{2c_v}{M}\right\rfloor \right) \, x(\delta ^+(v)) \\ =&\, \delta \cdot x(E(G)) + \sum _{v\in V(G)} \frac{2c_v}{M} \, x(\delta ^+(v)) \\ =&\,\delta \cdot x(E(G))+ \frac{1}{M} c(x) \end{aligned}$$

for some $\delta \in [0,1]$. Hence

$$\begin{aligned} c(x) \ \le \ M x'(E(G)), \end{aligned}$$

and for minimal solutions we have $x(E(G)) \le n^2$ by Lemma 8, which implies $\delta \cdot x(E(G)) \le n^2 = \varepsilon \frac{2c(V(G))}{M}\le \varepsilon \frac{c(x)}{M}$ and thus

$$\begin{aligned} M x'(E(G))\ \le \ (1+\varepsilon ) c(x). \end{aligned}$$

Because tours are integral LP solutions, and optimum LP solutions and optimum tours can be assumed to be minimal, this completes the proof of (i) and (ii). To prove (iii), observe that contracting the paths $P_v$ in a tour $F'$ yields a tour F as claimed. $\square$

This immediately implies:

Theorem 3

The integrality ratio of (ATSP LP) is the same for unweighted and for node-weighted instances. For any constants $\alpha \ge 1$ and $\varepsilon >0$, there is a polynomial-time $(\alpha +\varepsilon )$-approximation algorithm for node-weighted instances if there is a polynomial-time $\alpha$-approximation algorithm for unweighted instances.

Proof

The equality of the integrality ratio for unweighted and for node-weighted instances follows from Lemma 9(i) and (ii). Now suppose we have a polynomial-time $\alpha$-approximation algorithm for unweighted instances. Then for a node-weighted instance (G, c) we apply Lemma 9 with $\varepsilon '={\frac{\varepsilon }{\alpha }}$ and apply our $\alpha$-approximation algorithm to the resulting digraph $G'$. Let $F'$ be the resulting tour in $G'$. By (iii) of Lemma 9, this tour corresponds to a tour F in G such that

$$\begin{aligned} c(F) \ \le \ M|F'| \ \le \ \alpha \cdot M {\textsc {opt}}_{G'} \ \le \ (1+\varepsilon ')\alpha \cdot {\textsc {opt}}_{(G,c)} \ = \ (\alpha +\varepsilon )\cdot {\textsc {opt}}_{(G,c)}. \end{aligned}$$

$\square$

Fig. 7

Constructing a family of digraphs with integrality ratio arbitrarily close to 2 for ATSP with unit weights. For a fixed even number $l\ge 4$ we define graphs $G_0, G_1,\ldots$. The graph $G_0$ consists of a bidirected path of length l. Then we construct $G_i$ from $G_{i-1}$ as in the picture. The picture shows the construction for $l=4$; in general, there are l copies of the graph $G_{i-1}$ (shown in green). The blue wiggly paths indicate paths of length $d_i$, where $d_0 =0$ and $d_i = l^{i} -d_{i-1} -2$. Let $G_i'$ be the graph arising from $G_i$ by identifying the blue $v_i$-$v'_i$-path with the blue $w_i$-$w'_i$-path. Then for $i\rightarrow \infty$, the integrality ratio of $G_i'$ converges to $2-\frac{2}{l}$ (Boyd and Elliott–Magwood [1]) (color figure online)

Fig. 8

The graph $G_1'$ for $l=6$. An optimum LP solution has value 1 on the blue edges and value ${\frac{1}{2}}$ on all other edges and hence we have ${\textsc {lp}}= |V(G_1')|$ (color figure online)

In particular, this implies that the node-weighted instances from Boyd and Elliott–Magwood [1] can be transformed to unweighted instances whose integrality ratio tends to 2. For convenience we show these instances in Figs. 7 and 8. Figure 7 shows the general construction of the family of instances, Fig. 8 a concrete example. To obtain these instances we have replaced every vertex v in the node-weighted instances with node-weight $c_v$ by a path of length $2c_v -1$ similar to the proof of Lemma 9. So, contracting the blue paths of length $d_i$ in Fig. 7 and setting the node-weight of the resulting vertex to $\frac{d_i + 1}{2}$ and node-weights in $G_0$ to $\frac{1}{2}$ results in the instances from Boyd and Elliott–Magwood [1]. Then, LP solutions (and tours) in the node-weighted instance correspond to LP solutions (and tours) of the same cost in the unweighted instance. It seems that previously only unweighted instances with integrality ratio at most $\frac{3}{2}$ were known (e.g. Gottschalk [7]).

By splitting an arbitrary vertex into two copies s and t, both inheriting all incident edges, this also yields a family of unweighted digraph instances of ATSPP whose integrality ratio tends to two. We summarize:

Corollary 1

The integrality ratio for unweighted digraph instances is at least two, both for (ATSP LP) and (ATSPP LP).$\square$