Dr. Christian Komusiewicz (TU Berlin)

We study the following problem: Given a directed graph D=(V,A) and an undirected graph G=(V,E) find a directed path P of length at least one in D such that G[V(P)] is connected; we call such paths consistent. We study three different variants of this problem: deciding whether there is a any consistent path, finding a longest consistent path, and finding a shortest consistent path.

We show for example that the decision version of the problem is NP-hard even if G is a tree with three vertices of degree at least three. We also study the parameterized complexity of the problem with respect to the parameter path length k and show that the problem is W[1]-hard for k even if G is a tree and D is acyclic.

Back to the research colloquium site.