  We introduce the combinatorial optimization problem Time Disjoint Walks
(TDW), which has applications in collision-free routing of discrete objects
(e.g., autonomous vehicles) over a network. This problem takes as input a
digraph $G$ with positive integer arc lengths, and $k$ pairs of vertices that
each represent a trip demand from a source to a destination. The goal is to
find a walk and delay for each demand so that no two trips occupy the same
vertex at the same time, and so that a min-max or min-sum objective over the
trip durations is realized.
  We focus here on the min-sum variant of Time Disjoint Walks, although most of
our results carry over to the min-max case. We restrict our study to various
subclasses of DAGs, and observe that there is a sharp complexity boundary
between Time Disjoint Walks on oriented stars and on oriented stars with the
central vertex replaced by a path. In particular, we present a poly-time
algorithm for min-sum and min-max TDW on the former, but show that min-sum TDW
on the latter is NP-hard.
  Our main hardness result is that for DAGs with max degree $\Delta\leq3$,
min-sum Time Disjoint Walks is APX-hard. We present a natural approximation
algorithm for the same class, and provide a tight analysis. In particular, we
prove that it achieves an approximation ratio of $\Theta(k/\log k)$ on
bounded-degree DAGs, and $\Theta(k)$ on DAGs and bounded-degree digraphs.
