Finding detours is fixed-parameter tractable
From MaRDI portal
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.
Recommendations
Cites work
- A c^k n 5-approximation algorithm for treewidth
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Color-coding
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Divide-and-Color
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Faster Algebraic Algorithms for Path and Packing Problems
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Graph minors. V. Excluding a planar graph
- Graph theory
- Improved algorithms for path, matching, and packing problems
- Large independent sets in subquartic planar graphs
- Large independent sets in triangle-free planar graphs
- Linear kernels and linear-time algorithms for finding large cuts
- Low polynomial exclusion of planar graph patterns
- Mixing Color Coding-Related Techniques
- Narrow sieves for parameterized paths and packings
- On limited nondeterminism and the complexity of the V-C dimension
- On Linear Time Minor Tests with Depth-First Search
- On the complexity of k-SAT
- Parameterized algorithms
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterizing above or below guaranteed values
- Polynomial bounds for the grid-minor theorem
- Polynomial kernels for -extendible properties parameterized above the Poljak-Turzík bound
- Quickly excluding a planar graph
- Randomized divide-and-conquer: improved path, matching, and packing algorithms
- Solving MAX-\(r\)-SAT above a tight lower bound
- The directed grid theorem
- Towards tight(er) bounds for the excluded grid theorem
- Tree-width and planar minors
- Vertex cover problem parameterized above and below tight bounds
Cited in
(10)- The tree longest detour problem in a biconnected graph.
- The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
- Adapting the directed grid theorem into an FPT algorithm
- Finding detours is fixed-parameter tractable
- Going far from degeneracy
- scientific article; zbMATH DE number 7765417 (Why is no real title available?)
- Detours in directed graphs
- Long directed detours: reduction to 2-disjoint paths
- Approximating long cycle above Dirac's guarantee
- A fast algorithm for maximum satisfiability above half number of clauses
This page was built for publication: Finding detours is fixed-parameter tractable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972756)
