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
consists of a spanning tree together with an additional edge joining vertex
to another vertex
. 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 , and that the time-dependent cost function c is symmetric, i.e., holds for all , , making the cost function c correspond to the undirected edges of . We consider a spanning tree of . For each vertex , there exists a unique -path in T, enabling us to define an arrival time induced by T via for each . Based on these arrival times we define the following:
The corresponding optimization problem asks for the value of a TDMST for an instance . 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 -hard problem itself:
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.
The TDMST construction used to prove Theorem A1.
Consider an instance of the 3Sat
problem (see [29
] (p. 391)), given in terms of a set
of Boolean variables and a set
of clauses, each clause consisting of exactly three literals in
. We construct a suitable instance of the TDMST problem using a number of components. First we define a component
for each variable
. The component is shown in Figure A1
a, the edges being annotated with their (constant) travel times.
We define a component for each clause . To this end, let , , denote the variables whose literals appear in and . The edges in the component have the following travel times:
The edges and have a constant travel time of 1.
has a travel time of
The same holds true for the edges and .
The travel time of the edge connecting
depends on whether
appears in the clause
. 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 set to true we choose the path in component . If the variable is set to false we choose the path to be part of the spanning tree. Thus, the arrival time of the tree at is 1 if is set to true and 2 otherwise. For each clause we add the edges between the vertices corresponding to its variables and their respective counterparts. Since the clause is satisfied, the arrival time at one of , , or is at most 2, enabling us to add the edges , , and at a cost of 1 each. The total cost of the resulting tree is at most .
Conversely, consider a tree T with costs less than M. We first consider the -paths in T for all . If this path does not contain itself, then it must start by t traversing a variable gadget for continued by a clause gadget , entering via and leaving via . As was established above, the earliest arrival time at is 2, implying that the time of arrival at is at least 4, resulting in a travel time of at least M for the traversal of edge , thereby contradicting the assumption of . For the same reason, T must contain either the path or . Based on the optimality of T, the tree must contain 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 one of the edges , say , is in T and directed away from . Since , the travel time of this edge must be less than M, implying that the arrival time of T at is at most 2. If appears in , then the arrival time at is 1, and the variable is set to true satisfying . If appears in , then it follows that the arrival time at is 2, the variable is set to false and clause is satisfied as well.
Now assume the existence of an -approximation for the TDMST problem. We construct the instance introduced above for 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 , and the instance is not satisfiable. □