Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, September 28, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Michael Hoffmann
Given a simple undirected graph G=(V,E), a positive integer k, and three distinct vertices s, t, and v from V, is there a chordless path from s via v to t in G that consists of at most k vertices? In a chordless path, no two vertices are connected by an edge that is not in the path. (Such paths are also known as induced paths.)
I will discuss the complexity of this problem that has been raised in the context of service deployment in communication networks. In particular, I will show that it is "unlikely" that this problem can be solved in f(k)*p(n) time, for some arbitrary (e.g., doubly exponential) function f and some polynomial p.
Similar results can be obtained for a number of related problems about chordless paths, for example, for deciding on the existence of a single directed chordless (s,t)-path in a digraph.
Automatic MiSe System Software Version 1.4803M | admin login