The Computational Complexity of Routing with Collision Avoidance
Marco T. Morik (TU Berlin)
In this talk, I provide an overview on the content of my Bachelor thesis. To be precise, I introduce the Minimum Time-Shared Edges (MTSE) problem: given a graph, two distinct vertices (the terminals), and two integers p and k, the question is whether there are p paths connecting the two terminals while sharing at most k edges. Considering a path as a sequence of edges, we say that an edge is shared if the edge appears in at least two paths at the same position in their corresponding sequence. It extends the NP-hard Minimum Shared Edges problem introduced by Omran et al. [J. Comb. Optim 2013] by a discrete time component.
In my thesis I studied the complexity not only for paths, where each vertex appears at most once, but also for trails, where each edge appears at most once, and walks, where vertices and edges can appear arbitrarily often. I show that MTSE on both undirected and directed planar graphs for trails and paths is NP-complete even if the number of shared edges k=0. Additionally, I present a polynomial-time algorithm for MTSE on directed acyclic graphs with the number of shared edges k=0.
Back to the research colloquium site.