TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 30.08.2017


Page Content

to Navigation

The Complexity of Routing with Few Collisions

Marco Morik (TU Berlin)

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.

This is a joint work with Till Fluschnik and Manuel Sorge.


Marco Morik
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe