University of Primorska
Faculty of Mathematics, Natural Sciences and Information Technologies
Datum / Date: 3.6.24
Čas / Time: 15:00-16:00
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Petr Golovach (University of Bergen)
Naslov / Title: Detours in Directed Graphs
Povzetek / 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