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 subset W of V: the waypoints. This waypoint routing problem finds immediate applications in the context of modern computer 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 (i.e., on grid graphs of maximum degree 3 and with slightly more waypoints) are computationally intractable.

Top