Title: Walking Through Waypoints,
Abstract: We initiate the study of a fundamental combinatorial problem: Given a
capacitated graph $G=(V,E)$, find a shortest walk ("route") from a source $s\in
V$ to a destination $t\in V$ that includes all vertices specified by a set
$\mathscr{W}\subseteq V$: the \emph{waypoints}. This waypoint routing problem
finds immediate applications in the context of modern networked distributed
systems. Our main contribution is an exact polynomial-time algorithm for graphs
of bounded treewidth. We also show that if the number of waypoints is
logarithmically bounded, exact polynomial-time algorithms exist even for
general graphs. Our two algorithms provide an almost complete characterization
of what can be solved exactly in polynomial-time: we show that more general
problems (e.g., on grid graphs of maximum degree 3, with slightly more
waypoints) are computationally intractable.