The complexity of routing with collision avoidance

摘要

We study the computational complexity of routing multiple objects through a network while avoiding collision: Given a graph G with two distinct terminals and two positive integers p,k, the question is whether one can connect the terminals by at least p routes (walks, trails, paths; the latter two without repeated edges or vertices, respectively) such that in at most k edges it happens that we traverse them in more than one route at the same time. We prove that for paths and trails the problem is NP-hard on undirected and directed planar graphs even if the maximum vertex degree or k≥0 is constant. For walks we prove polynomial-time solvability on undirected graphs for unbounded k and on directed graphs if k≥0 is constant. We additionally study variants where the maximum length of a route is restricted. For walks this variant becomes NP-hard on undirected graphs.