  The $k$-Detour problem is a basic path-finding problem: given a graph $G$ on
$n$ vertices, with specified nodes $s$ and $t$, and a positive integer $k$, the
goal is to determine if $G$ has an $st$-path of length exactly $\text{dist}(s,
t) + k$, where $\text{dist}(s, t)$ is the length of a shortest path from $s$ to
$t$. The $k$-Detour problem is NP-hard when $k$ is part of the input, so
researchers have sought efficient parameterized algorithms for this task,
running in $f(k)\text{poly}(n)$ time, for $f$ as slow-growing as possible.
  We present faster algorithms for $k$-Detour in undirected graphs, running in
$1.853^k \text{poly}(n)$ randomized and $4.082^k \text{poly}(n)$ deterministic
time. The previous fastest algorithms for this problem took $2.746^k
\text{poly}(n)$ randomized and $6.523^k \text{poly}(n)$ deterministic time
[Bez\'akov\'a-Curticapean-Dell-Fomin, ICALP 2017]. Our algorithms use the fact
that detecting a path of a given length in an undirected graph is easier if we
are promised that the path belongs to what we call a "bipartitioned" subgraph,
where the nodes are split into two parts and the path must satisfy constraints
on those parts. Previously, this idea was used to obtain the fastest known
algorithm for finding paths of length $k$ in undirected graphs
[Bj\"orklund-Husfeldt-Kaski-Koivisto, JCSS 2017].
  Our work has direct implications for the $k$-Longest Detour problem: in this
problem, we are given the same input as in $k$-Detour, but are now tasked with
determining if $G$ has an $st$-path of length at least $\text{dist}(s, t) + k.$
Our results for k-Detour imply that we can solve $k$-Longest Detour in $3.432^k
\text{poly}(n)$ randomized and $16.661^k \text{poly}(n)$ deterministic time.
The previous fastest algorithms for this problem took $7.539^k \text{poly}(n)$
randomized and $42.549^k \text{poly}(n)$ deterministic time [Fomin et al.,
STACS 2022].
