2024-06-03
15:00-16:00
FAMNIT-MP1
Petr Golovach (University of Bergen)
Detours in Directed Graphs
We study the ”above guarantee” version of the classical Longest Path problem on undirected and directed graphs called Longest Detour where the task is to decide whether a graph has an (s,t)-path of length at least dist_G(s,t)+k. Bezáková et al. in 2019 proved that on undirected graphs, the problem is fixed-parameter tractable (FPT). We establish a connection between Longest Detour and Disjoint Paths on directed graphs. Using these new insights, we design a 2^{O(k)} n^{O(1)} time algorithm for the problem on directed planar graphs. Furthermore, the new approach yields a significantly faster FPT algorithm on undirected graphs.
Joint work with Fedor V. Fomin, William Lochet, Danil Sagunov, Saket Saurabh, and Kirill Simonov