Finding Detours is Fixed-parameter Tractable

Abstract

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 problem Longest Detour 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 Longest Detour 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 the 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, and a deterministic algorithm with running time about 6.745^k, showing that this problem is FPT as well. Our algorithms for Exact Detour apply to both undirected and directed graphs.

Extended abstract appears at ICALP 2017

References in corpus (2)

• A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• Maximum Edge-Disjoint Paths in $k$-sums of Graphs

Cited by in corpus (7)

• (Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 1 : Layered wheels
• Quantum Advantage with Shallow Circuits Under Arbitrary Corruption
• Packing and Covering Immersion Models of Planar subcubic Graphs
• Structural properties of bipartite subgraphs
• Erdös-Pósa property of minor-models with prescribed vertex sets
• The Half-integral Erdös-Pósa Property for Non-null Cycles
• Extension Complexity of the Correlation Polytope