Relaxations play an important role in integer programming in general and the TSP in particular. They provide lower bounds which can be used to obtain quality guarantees for solutions. The prevalent relaxation of combinatorial problems formulated as integer programs is given by their fractional relaxations. In several cases however, it is possible to derive purely combinatorial relaxations. In case of the symmetric traveling salesman problem, a popular combinatorial relaxation is given by one-trees [

31]. A one-tree with respect to a graph

$G=(V,E)$ with

$V=\{1,\dots ,n\}$ consists of a spanning tree together with an additional edge joining vertex

$s:=1$ to another vertex

$v\in V$. Since every tour is a one-tree, the one-tree of minimum cost provides a lower bound on the cost of a tour. The computation of such a one-tree in the static case involves the computation of a minimum spanning tree (MST), which can be carried out efficiently. The approach generalizes to the ATSP, in which case the one-tree corresponds to an arborescence with root

s together with a single arc entering

s from another vertex

v.

An important question to ask is whether these approaches carry over to the time-dependent case. We begin by generalizing the definition of spanning trees to the time-dependent case. To this end, we assume throughout this subsection that D is bidirected, corresponding to an undirected graph ${G}_{D}$, and that the time-dependent cost function c is symmetric, i.e., ${c}_{uv}\left(\theta \right)={c}_{vu}\left(\theta \right)$ holds for all $(u,v)\in A$, $\theta \in \Theta $, making the cost function c correspond to the undirected edges of ${G}_{D}$. We consider a spanning tree $T=(V,F)$ of ${G}_{D}$. For each vertex $v\in V$, there exists a unique $(s,v)$-path ${P}_{v}$ in T, enabling us to define an arrival time ${\theta}_{T}^{arr}\left(u\right)$ induced by T via ${P}_{u}$ for each $u\in V$. Based on these arrival times we define the following:

The corresponding optimization problem asks for the value of a TDMST for an instance $({G}_{D},c,s)$. As was the case before, any tour becomes a spanning tree once we remove its last arc, the arrival time of the resulting path at its target coinciding with the cost of the tree. Consequently, the optimal value of the corresponding TDTSP instance is bounded from below by the cost of any minimum spanning tree. Unfortunately, approximating the TDMST is an $\mathcal{NP}$-hard problem itself:

**Figure A1.**
Gadgets used in the proof of Theorem A1. (**a**) A component which queries whether a variable is set; (**b**) A component which determines whether a clause is satisfied.

**Figure A2.**
The TDMST construction used to prove Theorem A1.

**Proof.** Consider an instance of the

3Sat problem (see [

29] (p. 391)), given in terms of a set

$X:=\{{x}_{1},\dots ,{x}_{n}\}$ of Boolean variables and a set

$\mathcal{Z}:=\{{Z}_{1},\dots ,{Z}_{m}\}$ of clauses, each clause consisting of exactly three literals in

$X\dot{\cup}\overline{X}$. We construct a suitable instance of the TDMST problem using a number of components. First we define a component

${A}_{i}$ for each variable

${x}_{i}\in X$. The component is shown in

Figure A1a, the edges being annotated with their (constant) travel times.

We define a component ${B}_{i}$ for each clause ${Z}_{i}\in \mathcal{Z}$. To this end, let ${x}_{i1}$, ${x}_{i2}$, ${x}_{i3}$ denote the variables whose literals appear in ${Z}_{i}$ and $M\ge 2n+6m+1$. The edges in the component have the following travel times:

The edges $\{{w}_{i1},{w}_{i2}\}$ and $\{{w}_{i2},{w}_{i3}\}$ have a constant travel time of 1.

The edge

$\{{v}_{i1},{w}_{i1}\}$ has a travel time of

The same holds true for the edges $\{{v}_{i2},{w}_{i2}\}$ and $\{{v}_{i3},{w}_{i3}\}$.

The travel time of the edge connecting

${x}_{ik}$ and

${v}_{ik}$ depends on whether

${x}_{k}$ or

${\overline{x}}_{k}$ appears in the clause

${Z}_{j}$. In the former case the travel time is constantly 1, whereas in the latter it is given by

The instance including the components, depicted in

Figure A2, has a TDMST of cost less than

M if and only if the

3Sat instance is satisfiable:

Consider a satisfying truth assignment of the 3Sat instance. For each variable ${x}_{j}$ set to `true` we choose the path $(s,{s}_{j},{x}_{j},{t}_{j})$ in component ${A}_{j}$. If the variable is set to `false` we choose the path $(s,{s}_{j},{t}_{j},{x}_{j})$ to be part of the spanning tree. Thus, the arrival time of the tree at ${x}_{j}$ is 1 if ${x}_{j}$ is set to `true` and 2 otherwise. For each clause ${Z}_{i}$ we add the edges between the vertices corresponding to its variables and their respective ${v}_{i}$ counterparts. Since the clause is satisfied, the arrival time at one of ${v}_{i1}$, ${v}_{i2}$, or ${v}_{i3}$ is at most 2, enabling us to add the edges $\{{v}_{ik},{w}_{ik}\}$, $\{{w}_{i1},{w}_{i2}\}$, and $\{{w}_{i2},{w}_{i3}\}$ at a cost of 1 each. The total cost of the resulting tree is at most $2n+6m<M$.

Conversely, consider a tree T with costs less than M. We first consider the $(s,{s}_{j})$-paths in T for all $j=1,\dots ,n$. If this path does not contain $\{s,{s}_{j}\}$ itself, then it must start by t traversing a variable gadget ${A}_{{j}^{\prime}}$ for ${j}^{\prime}\ne j$ continued by a clause gadget ${B}_{i}$, entering via ${v}_{ik}$ and leaving via ${v}_{il}$. As was established above, the earliest arrival time at ${v}_{ik}$ is 2, implying that the time of arrival at ${w}_{il}$ is at least 4, resulting in a travel time of at least M for the traversal of edge $\{{w}_{il},{v}_{il}\}$, thereby contradicting the assumption of $c\left(T\right)<M$. For the same reason, T must contain either the path $(s,{s}_{j},{x}_{j})$ or $(s,{s}_{j},{t}_{j},{x}_{j})$. Based on the optimality of T, the tree must contain $(s,{s}_{j},{x}_{j},{t}_{j})$ in the former case. We can therefore identify the choice of paths with a variable assignment as we did above.

To see that the assignment is feasible, we note that for each clause ${Z}_{i}$ one of the edges $\{{v}_{ik},{w}_{ik}\}$, say $\{{v}_{i1},{w}_{i1}\}$, is in T and directed away from ${v}_{i1}$. Since $c\left(T\right)<M$, the travel time of this edge must be less than M, implying that the arrival time of T at ${v}_{i1}$ is at most 2. If ${x}_{i1}$ appears in ${Z}_{j}$, then the arrival time at ${x}_{i1}$ is 1, and the variable is set to `true` satisfying ${Z}_{i}$. If ${\overline{x}}_{i1}$ appears in ${Z}_{j}$, then it follows that the arrival time at ${x}_{i1}$ is 2, the variable is set to `false` and clause ${Z}_{i}$ is satisfied as well.

Now assume the existence of an $\alpha $-approximation for the TDMST problem. We construct the instance introduced above for $M:=\lceil \alpha \phantom{\rule{0.166667em}{0ex}}\xb7\phantom{\rule{0.166667em}{0ex}}(2n+6m)\rceil $ and apply the approximation. If the resulting tree has costs less than M, the 3Sat instance is satisfiable. Otherwise, the optimal TDMST has costs at least $M/\alpha \ge 2n+6m$, and the instance is not satisfiable. □