Long Directed Detours: Reduction to 2-Disjoint Paths
share
We study an "above guarantee" version of the Longest Path problem in directed graphs: We are given a graph G, two vertices s and t of G, and a non-negative integer k, and the objective is to determine whether G contains a path of length at least dist_G(s,t) +k where dist_G(s,t) is the length of a shortest path from s to t in G (assuming that one exists). We show that the problem is fixed parameter tractable (FPT) parameterized by k in the class of graphs where 2-Disjoint Paths problem is polynomial time solvable.
READ FULL TEXT