Prof. Meirav Zehavi

In the LONGEST (s,t)-DETOUR problem, we look for an (s,t)-path that is at least k vertices longer than a shortest one. We study the parameterized complexity of LONGEST (s,t)-DETOUR when parameterized by k: this falls into the research paradigm of ‘parameterization above guarantee’. Whereas the problem is known to be fixed-parameter tractable (FPT) on undirected graphs, the status of LONGEST (s,t)-DETOUR on directed graphs remains highly unclear: it is not even known to be solvable in polynomial time for k=1. Recently, Fomin et al. made progress in this direction by showing that the problem is FPT on every class of directed graphs where the 3-DISJOINT PATHS problem is solvable in polynomial time. We improve upon their result by weakening this assumption: we show that only a polynomial-time algorithm for 2-DISJOINT PATHS is required.