Datum in ura / Date and time: 3.6.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Petr Golovach (University of Bergen)
Naslov / Title: Detours in Directed Graphs
Vsebina / Abstract:
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