  We study the computational complexity of routing multiple objects through a
network in such a way that only few collisions occur: Given a graph $G$ with
two distinct terminal vertices and two positive integers $p$ and $k$, the
question is whether one can connect the terminals by at least $p$ routes (e.g.
paths) such that at most $k$ edges are time-wise shared among them. We study
three types of routes: traverse each vertex at most once (paths), each edge at
most once (trails), or no such restrictions (walks). We prove that for paths
and trails the problem is NP-complete on undirected and directed graphs even if
$k$ is constant or the maximum vertex degree in the input graph is constant.
For walks, however, it is solvable in polynomial time on undirected graphs for
arbitrary $k$ and on directed graphs if $k$ is constant. We additionally study
for all route types a variant of the problem where the maximum length of a
route is restricted by some given upper bound. We prove that this
length-restricted variant has the same complexity classification with respect
to paths and trails, but for walks it becomes NP-complete on undirected graphs.
