Name
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 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1137/17m1148566 | international colloquium on automata, languages and programming |
DocType | Volume | Issue |
Journal | 33 | 4 |
Citations | PageRank | References |
1 | 0.38 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ivona Bezáková | 1 | 141 | 19.66 |
| Radu Curticapean | 2 | 70 | 8.75 |
| Holger Dell | 3 | 220 | 16.74 |
| Fedor V. Fomin | 4 | 3139 | 192.21 |