2026-07-23T20:02:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7479 2024-03-06T10:40:22Z ddc:004 open_access

Finding Detours is Fixed-Parameter Tractable Bezáková, Ivona Curticapean, Radu Dell, Holger Fomin, Fedor V. longest path fixed-parameter tractable algorithms above-guarantee parameterization graph minors We consider the following natural "above guarantee" parameterization of the classical longest path problem: For given vertices s and t of a graph G, and an integer k, the longest detour problem asks for an (s,t)-path in G that is at least k longer than a shortest (s,t)-path. Using insights into structural graph theory, we prove that the longest detour problem is fixed-parameter tractable (FPT) on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time exp(O(k)) * poly(n). This matches (up to the base of the exponential) the best algorithms for finding a path of length at least k. Furthermore, we study a related problem, exact detour, that asks whether a graph G contains an (s,t)-path that is exactly k longer than a shortest (s,t)-path. For this problem, we obtain a randomized algorithm with running time about 2.746^k * poly(n), and a deterministic algorithm with running time about 6.745^k * poly(n), showing that this problem is FPT as well. Our algorithms for the exact detour problem apply to both undirected and directed graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ivona Bezáková and Radu Curticapean and Holger Dell and Fedor V. Fomin 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.54 urn:nbn:de:0030-drops-74790 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.54 eng https://creativecommons.org/licenses/by/3.0/legalcode