# Long Directed Detours: Reduction to $2$-Disjoint Paths111It has recently
come to our attention that a similar result is given in [15]. Our work was
conducted independently of this work. 222This work was supported by the
European Research Council (ERC) grant titled PARAPATH.

Ashwin Jacob  Ben Gurion University of the Negev, Beersheba, Israel
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Michał Włodarczyk  Ben Gurion University of the Negev,
Beersheba, Israel<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Meirav Zehavi  Ben Gurion University of the Negev,
Beersheba, Israel<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

In the Longest $(s,t)$-Detour problem, we look for an $(s,t)$-path that is at
least $k$ vertices longer than a shortest one. We study the parameterized
complexity of Longest $(s,t)$-Detour when parameterized by $k$: this falls
into the research paradigm of ‘parameterization above guarantee’. Whereas the
problem is known to be fixed-parameter tractable (FPT) on undirected graphs,
the status of Longest $(s,t)$-Detour on directed graphs remains highly
unclear: it is not even known to be solvable in polynomial time for $k=1$.
Recently, Fomin et al. made progress in this direction by showing that the
problem is FPT on every class of directed graphs where the 3-Disjoint Paths
problem is solvable in polynomial time. We improve upon their result by
weakening this assumption: we show that only a polynomial-time algorithm for
2-Disjoint Paths is required. What is more, our approach yields an arguably
simpler proof.

##  1 Introduction

In the Longest Path problem, given a (directed or undirected) graph $G$ and a
non-negative integer $k$, the objective is to determine whether $G$ contains a
(simple) path of length at least $k$. For over more than three decades, this
problem has been studied extensively in the field of parameterized complexity,
and has led to the development of various algorithmic techniques such as
color-coding, algebraic methods and representative sets [2, 17, 22, 18, 11].

A recent trend in parameterized complexity is to consider above guarantee
versions of Longest Path and its variants where the parameter is the
difference between $k$ and some guarantee. Hence, the length of the sought
path could be potentially large while the parameter is small. One such example
is the Longest $(s,t)$-Detour problem, where we are also given two vertices
$s$ and $t$ of $G$, and the objective is to determine whether $G$ contains a
path from $s$ to $t$ of length at least $dist_{G}(s,t)+k$, where
$dist_{G}(s,t)$ is the length of a shortest path from $s$ to $t$ in $G$
(assuming that one exists) and the parameter is $k$.

Let $\mathcal{C}$ be the class of directed graphs where $2$-Disjoint Paths
problem is polynomial-time solvable. We show that the Longest $(s,t)$-Detour
problem is FPT in directed graphs in $\mathcal{C}$.

The Longest $(s,t)$-Detour problem was first studied by Bezakova et. al. [3],
where they showed that the problem is FPT in undirected graphs. They also
proved that the Exact $(s,t)$-Detour problem, where we check for an
$(s,t)$-path of length exactly $dist_{G}(s,t)+k$, is solvable in
$6.745^{k}n^{{\mathcal{O}}(1)}$ time for directed and undirected graphs.
Later, Fomin et. al. [7] showed that the Longest $(s,t)$-Detour problem is
solvable in $45.5^{k}n^{{\mathcal{O}}(1)}$ time for directed graphs in graph
classes where the $3$-Disjoint Paths problem is polynomial-time solvable.
Thus, we improve the requirement of solvability of $3$-Disjoint Paths to the
solvability of $2$-Disjoint Paths. We note that for directed graphs in
general, it is not even known whether the problem is in P or NP-hard for $k=1$
[3, 7, 14].

Related Work. The paradigm of “above guarantee” parameterizations of problems
was introduced by Mahajan and Raman [20]. Since then, such parameterizations
were studied for a wide variety of problems, such as Vertex Cover [19, 13],
Max Sat [20], Max Cut [1, 20] and Multiway Cut [4], to name a few.

Other “above guarantee” versions of the Longest Path and Longest Cycle
problems were studied in the literature for undirected graphs. Fomin et al.
[8] gave an algorithm to find paths (cycles) of length $d+k$ in a connected
($2$-connected) $d$-degenerate graph in
$2^{{\mathcal{O}}(k)}n^{{\mathcal{O}}(1)}$ time. Jansen et al. [16] showed
that the Hamiltonian Cycle problem can be solved in
$2^{{\mathcal{O}}(k)}n^{{\mathcal{O}}(1)}$ time, if at least $n-k$ vertices
have degree at least $n/2$, or if all vertices have degree at least $n/2-k$ (a
relaxation of the famous Dirac’s Theorem [6]). For the first parameterization,
they did so by giving an ${\mathcal{O}}(k)$ kernel. Recently, Fomin et al.
[10] considered a more general relaxation of Dirac’s Theorem. They showed that
given a $2$-connected graph $G$ and a subset $B\subseteq V(G)$, finding a
cycle of length at least $\min\\{2\delta(G-B),n-|B|\\}+k$ for minimum degree
function $\delta$ can be solved in
$2^{{\mathcal{O}}(k+|B|)}n^{{\mathcal{O}}(1)}$ time. Further, Fomin et al. [9]
gave an algorithm to find paths and cycles of length at least $g\cdot k$ where
$g$ is the girth of the graph in $2^{{\mathcal{O}}(k^{2})}n$ time.

##  2 Preliminaries

General Notation. Let $\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$, where
$\mathbb{N}$ is the set of natural numbers. Given $r\in\mathbb{N}_{0}$, let
$[r]=\\{1,\ldots,r\\}$, and given $r_{1},r_{2}\in\mathbb{N}_{0}$, let
$[r_{1},r_{2}]=\\{r_{1},r_{1}+1,\ldots,r_{2}\\}$. Given a finite set $A$ and
an integer $t\in\mathbb{N}_{0}$, let $2^{A}$ denote the family of all subsets
of $A$, and let ${{A}\choose{t}}$ and ${{A}\choose{\leq t}}$ denote the family
of all subsets of $A$ size exactly $t$ and at most $t$, respectively.

Graphs. We use standard graph theoretic terminology from Diestel’s book [5].
For a directed or undirected graph $G=(V,E)$, let $V(G)$ denote the set of
vertices of $G$, and $E(G)$ the set of edges of $G$. When $G$ is clear from
context, let $n=|V(G)|$ and $m=|E(G)|$. For a set $X\subseteq G$, let $G[X]$
denote the subgraph of $G$ induced on the vertex set $X$, and $G-X$ denote the
subgraph of $G$ induced on the vertex set $V(G)\setminus X$. For an edge
$e=(u,v)$ in a directed graph, we say that $v$ is an outneighbor of $u$ and
$u$ is an inneighbor of $v$.

A walk (in a given graph $G$) is a sequence of vertices $v_{0},\ldots,v_{k}$
such that for every $i\in\\{0,\ldots,k-1\\}$ we have $(v_{i},v_{i+1})\in
E(G)$. The walk is closed if $v_{0}=v_{k}$. A path is a walk where no vertex
appears more than once. A cycle is a closed walk where no vertex appears more
than once, apart from $v_{0}$ and $v_{k}$ (which are the same vertex). The
length of a path (or a cycle) $P$ is the number of edges in $P$, and it is
denoted by $|P|$. The girth of a graph $G$ is the shortest length of a cycle
in $G$. If the first and last vertices of $P$ are $s$ and $t$, respectively,
we call it an $(s,t)$-path. If an $(s,t)$-path has the shortest length among
all the $(s,t)$-paths in the graph $G$, we call the path a shortest
$(s,t)$-path in $G$ (or just shortest $(s,t)$-path if $G$ is clear from
context). For a path $P$, let us denote the subpath between any two vertices
$u_{1}$ and $u_{2}$ of $P$ as $P_{u_{1},u_{2}}$. We say that the walk formed
by two paths $P_{1}$ and $P_{2}$ where the last vertex of $P_{1}$ is equal to
the first vertex of $P_{2}$ is the concatenation of $P_{1}$ and $P_{2}$,
denoted as $P_{1}\circ P_{2}$. A vertex $t$ is reachable from a vertex $s$ in
$G$ if there exists a path in $G$ that starts with $s$ and ends with $t$. The
distance between two vertices $s$ and $t$ in $G$, denoted by $dist_{G}(s,t)$,
is the number of edges in a shortest $(s,t)$-path in $G$ (defined as $\infty$
if no such path exists). When $G$ is clear from context, we drop the subscript
$G$ from $dist_{G}(s,t)$.

Parameterized Complexity. A parameterized problem $L$ is a subset of
$\Sigma^{*}\times\mathbb{N}_{0}$ for some finite alphabet $\Sigma$. Thus, an
instance of a parameterized problem is denoted by $(x,k)$ where
$x\in\Sigma^{*},k\in\mathbb{N}_{0}$. We denote by $|x|$ the length of $x$.

######  Definition 1 (Fixed-Parameter Tractability).

A parameterized problem $L$ is fixed-parameter tractable (FPT) if there exists
an algorithm ${\mathcal{A}}$, a computable function
$f:\mathbb{N}\rightarrow\mathbb{N}$ and a constant $c$ independent of $f$ and
$k$, such that given input $(x,k)$, ${\mathcal{A}}$ runs in time
${\mathcal{O}}(f(k)|x|^{c})$ and correctly decides whether $(x,k)\in L$.

Pseudorandom Object. We will use the following notion.

######  Definition 2 ($(n,p,q)$-Lopsided Universal Family).

Let $n,p,q\in\mathbb{N}_{0}$ such that $n\geq p+q$. A family ${\mathcal{F}}$
of sets over a universe $U$ of size $n$ is an $(n,p,q)$-lopsided universal
family if for every $A\in{U\choose\leq p}$ and $B\in{U\setminus A\choose\leq
q}$ there exists $F\in{\mathcal{F}}$ such that $A\subseteq F$ and $B\cap
F=\emptyset$.

######  Lemma 1 ([21]).

There is an algorithm that given $n,p,q\in\mathbb{N}_{0}$ such that $n\geq
p+q$, constructs an $(n,p,q)$-lopsided universal family ${\mathcal{F}}$ of
size ${p+q\choose p}\cdot 2^{o(p+q)}\cdot\log n$ in time ${p+q\choose p}\cdot
2^{o(p+q)}\cdot n\log n$.

Problem Definitions and Some Known Results. We now define the problems
relevant to our work. Here, the graph $G$ could be undirected or directed,
unless stated otherwise.

Longest $(s,t)$-Path Input: A graph $G=(V,E)$, vertices $s,t$ and a non-
negative integer $k$. Parameter: $k$ Question: Is there an $(s,t)$-path in $G$
of length at least $k$?

We have the following algorithm by Fomin et al. [12] for Longest $(s,t)$-Path
parameterized by the path length $k$ on directed graphs.

######  Theorem 1 ([12]).

Longest $(s,t)$-Path on directed (and undirected) graphs can be solved in
$4.884^{k}n^{{\mathcal{O}}(1)}$ time.

Longest $(s,t)$-Detour Input: A graph $G=(V,E)$, vertices $s,t$ and a non-
negative integer $k$. Parameter: $k$ Question: Is there an $(s,t)$-path in $G$
of length at least $dist_{G}(s,t)+k$?

The Longest $(s,t)$-Detour problem was previously studied by Bezakova et al.
[3]. The authors showed that the problem is FPT on undirected graphs.

$p$-Disjoint Paths Input: A graph $G=(V,E)$ and $p$ pairs of terminal vertices
$(s_{i},t_{i}),i\in\\{1,\dotsc,p\\}$ for a non-negative integer $p$. Question:
Is there a multiset $\mathcal{P}=\\{P_{i}:i\in[p],$ $P_{i}$ is an
$(s_{i},t_{i})$-path in $G\\}$ of paths that are vertex disjoint except
possibly at their endpoints? . Note that, here, two paths can share vertices
as long as these vertices are endpoints of both paths.

Fomin et al. [7] studied Longest $(s,t)$-Detour on directed graphs and proved
the following theorem.

######  Theorem 2 ([7]).

Let $\mathcal{C}$ be a class of graphs such that $3$-Disjoint Paths on
$\mathcal{C}$ can be solved in polynomial time. Then, Longest $(s,t)$-Detour
on $\mathcal{C}$ can be solved in $2^{{\mathcal{O}}(k)}n^{{\mathcal{O}}(1)}$
time.

Bezakova et al. [3] also gave an FPT algorithm for Exact $(s,t)$-Detour,
defined below.

Exact $(s,t)$-Detour Input: A graph $G=(V,E)$, vertices $s,t$ and a non-
negative integer $k$. Parameter: $k$ Question: Is there an $(s,t)$-path in $G$
of length exactly $dist_{G}(s,t)+k$?

######  Theorem 3 ([3]).

Exact Detour on directed (and undirected) graphs can be solved in
$6.745^{k}n^{{\mathcal{O}}(1)}$ time.

##  3 FPT Algorithm for Longest $(s,t)$-Detour

In this section, we improve upon Theorem 2: we define $\mathcal{C}$ as the
class of graphs where $2$-Disjoint Paths (rather than $3$-Disjoint Paths) can
be solved in polynomial time. Additionally, our algorithm has (arguably) a
simpler proof compared to that of Fomin et al. [7].

###  3.1 Algorithm

We present the pseudocode of our algorithm in Algorithm 1. On a high-level,
The algorithm calls Theorem 3 for Exact $(s,t)$-Detour over all values
$\ell\in[k,2k-1]$. Then, it iterates over every choice of three vertices
$u,v,x\in V(G)$ and subset $F\subseteq{\mathcal{F}}$, where ${\mathcal{F}}$ is
an $(n,k+1,3k+1)$-lopsided universal family over universe $V(G)$. For each
such choice, it constructs a path (if one exists) that is the concatenation
of:

  1. 1.

a shortest path from $s$ to $u$,

  2. 2.

a path of length $k$ from $u$ to $x$ whose vertices are within $F$ and has
distance at least $dist_{G}(s,u)$ from $s$, and

  3. 3.

two vertex disjoint paths from $x$ to $v$ and $v$ to $t$.

If such a path does not exist (for all choices), then the algorithm concludes
that we have a NO-instance.

Algorithm 1 Algorithm for Longest $(s,t)$-Detour on $\mathcal{C}$

Input: A directed graph $G=(V,E)$, vertices $s,t$, and a non-negative integer
$k$.

Output: YES if $G$ has an $(s,t)$-path of length at least $dist_{G}(s,t)+k$;
NO otherwise.

1:Check if $t$ is reachable from $s$. If not, return NO.

2:If $k=0$, return YES.

3:for $\ell\in[k,2k-1]$ do

4: Run the algorithm from Theorem 3 for parameter $\ell$. If the algorithm
returns YES, return YES.

5:end for

6:Compute $R\subseteq V(G)$, the set of vertices reachable from $s$ in $G$,
using breadth-first-search (BFS). Update $G$ to $G[R]$. Let layer $L_{i}$,
$0\leq i\leq r$, be the set of vertices at distance $i$ from $s$ in $G$, where
$r$ is the maximum distance of a vertex in $G$ from $s$.

7:Construct an $(n,k+1,3k+1)$-lopsided universal family ${\mathcal{F}}$ over
universe $V(G)$ using Lemma 1.

8:for $F\in{\mathcal{F}}$ do

9: for $p\in[r]$ and vertices $u,v,x\in V(G)$ where $u,v\in L_{p}$ do

10: Find a shortest $(s,u)$-path $P_{1}$.

11: Find a path $P_{2}$ from $u$ to $x$ of length $k$ in the graph
$G[F\cap\bigcup_{i\geq p}L_{i}]$ (if one exists) using the algorithm in
Theorem 1.

12: Check if in $G-(V(P_{1})\cup V(P_{2})\setminus\\{x\\})$ there are two
vertex disjoint paths, one from $x$ to $v$ and the other from $v$ to $t$,
using the polynomial time algorithm for $2$-Disjoint Paths on $\mathcal{C}$.
If the algorithm returns YES, return YES.

13: end for

14:end for

15:Return NO.

###  3.2 Correctness

Steps 1-5. We begin with the following observation.

######  Observation 1.

Steps 1-5 of Algorithm 1 are correct.

###### Proof.

The correctness of Step 1 follows as there is no $(s,t)$-path in $G$ if $t$ is
not reachable from $s$. Given that $t$ is reachable from $s$, by the
definition of $dist_{G}(s,t)$, there exists an $(s,t)$-path in $G$ of length
$dist_{G}(s,t)+k$ if $k=0$. Hence, Step 2 of the algorithm is correct as well.

The correctness of Steps 3-5 follows from Theorem 3. ∎

Steps 6-15. From here on, we suppose that the algorithm has reached Step 6. We
start with the following observation, which follows as the algorithm did not
terminate in Steps 3-5.

######  Observation 2.

Any solution path $P$ is of length at least $dist_{G}(s,t)+2k$.

Next, we identify two vertices in a (hypothetical) solution that will play a
central role in the rest of the proof (see Figure 1).

Figure 1: The shortest solution path $P$. Here, $L_{p}$ is the first layer
having multiple vertices of $P$, and vertices $u$ and $v$ are the first two
vertices of $P$ in this layer.

######  Definition 3.

Let $P$ be a solution path of shortest length. Let $p$ be the smallest integer
$i\in[r]$ such that $L_{i}$ contains more than one vertex of $P$. Let $u$ and
$v$ be the first and second vertices of $P$ in $L_{p}$.333 Since $t$ is in
layer $L_{dist_{G}(s,t)}$ and $P$ is of length at least $dist_{G}(s,t)+2k$ (in
particular, strictly larger than $dist_{G}(s,t)$), layer $L_{p}$ exists.

We remark that the algorithm by Fomin et al. [7] also identifies layer $L_{p}$
and vertices $u$ and $v$ for the solution path of shortest length $P$.

Note that in one of the iterations of Step 9, integer $p$ and vertices $u$ and
$v$ will be the ones defined in Definition 3. We have the following
observation regarding the length of the subpath of $P$ from $s$ to $u$.

######  Observation 3.

Let $P,p,u$ be as defined in Definition 3. The subpath $P_{s,u}$ of $P$ is a
shortest $(s,u)$-path.

###### Proof.

Any $(s,u)$-path must contain at least one vertex from each layer $L_{i}$ with
$0\leq i\leq p$. Recall that $p$ is the smallest integer $i\in[r]$ such that
$L_{i}$ contains more than one vertex of $P$, and $u$ is the first vertex of
$L_{p}$ in $P$. Thus, the subpath $P_{s,u}$ contains exactly one vertex from
each layer $L_{i}$ with $0\leq i<p$ and ends at $u\in L_{p}$. Hence, this
subpath is a shortest $(s,u)$-path. ∎

Next, we have the following lemma regarding the length of the subpath of $P$
from $u$ to $v$. The lemma statement was also proved by Fomin et al. [7]. But
we give the proof here nevertheless for the sake of completeness.

######  Lemma 2.

Let $P,u,v$ be as defined in Definition 3. The length of the subpath $P_{u,v}$
of $P$ is larger than $k$.

###### Proof.

Targeting a contradiction, suppose the subpath $P_{u,v}$ of $P$ has length at
most $k$. Then, the length of the subpath $P_{s,v}=P_{s,u}\circ P_{u,v}$,
being $|P_{s,u}|+|P_{u,v}|$, is at most $dist(s,u)+k$ ($|P_{s,u}|=dist(s,u)$
from Observation 3). Since $P=P_{s,v}\circ P_{v,t}$, it follows that the
length of the subpath $P_{v,t}$, being $|P|-|P_{s,v}|$, is at least
$dist(s,t)+2k-dist(s,u)-k$.

Let $P^{\prime}$ be the walk formed by concatenating an arbitrary shortest
$(s,v)$-path $\hat{P}$ with the subpath $P_{v,t}$ of $P$. Note that any
shortest $(s,v)$-path consists only of vertices from layers $L_{i}$ with
$0\leq i<p$ except the vertex $v$. Moreover, by the definitions of $L_{p}$ and
$v$, the subpath $P_{v,t}$ consists only of vertices from layers $L_{i}$ with
$i\geq p$. Thus, $P_{v,t}$ is vertex disjoint from $\hat{P}$ (except for the
endpoint $v$, which is the only common vertex). Therefore, the walk
$P^{\prime}$ is a path. From Observation 3, we know that the subpath $P_{s,u}$
is a shortest $(s,u)$-path. So, $P=P_{s,u}\circ P_{u,v}\circ P_{v,t}$,
$P^{\prime}=\hat{P}\circ P_{v,t}$ and $|P_{s,u}|=|\hat{P}|$. Hence, the path
$P^{\prime}$ is of length $|P|-|P_{u,v}|$, which is at least
$dist(s,t)+2k-k>dist(s,t)+k$. However, $P^{\prime}$ is shorter than $P$ as
there is at least one edge in the subpath $P_{u,v}$. This contradicts that $P$
is a solution path of shortest length (as defined in Definition 3). ∎

Next, we identify three additional vertices in the (hypothetical) solution
path $P$ (see Figure 2).

Figure 2: The shortest solution path $P$ with vertices $x,y$ and $z$ as
defined in Definition 4.

######  Definition 4.

Let $P,u,v$ be as defined in Definition 3. Let $x$ be last vertex of the
subpath induced on the first $k+1$ vertices of $P_{u,v}$ (hence, the length of
$P_{u,x}$ is $k$). Also, let $y$ be the first vertex of the subpath induced on
the last $k^{\prime}$ vertices of $P_{u,v}$ where
$k^{\prime}=\min\\{k+1,|V(P_{x,v})|\\}$. Finally, let $z$ be the last vertex
of the subpath of $P_{v,t}$ induced on the first $k^{\prime\prime}$ verices of
$P_{v,t}$ where $k^{\prime\prime}=\min\\{2k+1,|V(P_{v,t})|\\}$.

Note that $x$ exists as the length of $P_{u,v}$ is larger than $k$ from Lemma
2. We remark that in one of the iterations of Step 9, the vertex $x$ will be
the one defined in Definition 4. Also, $y=x$ when $k^{\prime}=|V(P_{x,v})|$,
and $z=t$ when $k^{\prime\prime}=|V(P_{v,t})|$.

We have the following lemma regarding $P_{u,x}$ and $P_{y,z}$.

######  Observation 4.

Let ${\mathcal{F}}$ be the $(n,k+1,3k+1)$-lopsided universal family over
universe $V(G)$ constructed in Step 7. Then,

  * •

if $y\neq x$, there exists $F\in{\mathcal{F}}$ such that $V(P_{u,x})\subseteq
F$ and $V(P_{y,z})\cap F=\emptyset$.

  * •

if $y=x$, there exists $F\in{\mathcal{F}}$ such that $V(P_{u,x})\subseteq F$
and $(V(P_{y,z})\setminus\\{x\\})\cap F=\emptyset$.

###### Proof.

For the first case, we have $|V(P_{u,x})|=k+1$ and
$|V(P_{y,z})|=|V(P_{y,v})|+|V(P_{v,z})|-1=k^{\prime}+k^{\prime\prime}-1\leq
k+1+2k+1-1=3k+1$. Moreover, $V(P_{u,x})\cap V(P_{y,z})=\emptyset$. So, by the
definition of $(n,k+1,3k+1)$-lopsided universal family over universe $V(G)$,
there exists $F\in{\mathcal{F}}$ such that $V(P_{u,x})\subseteq F$ and
$V(P_{y,z})\cap F=\emptyset$. The statement follows for the second case as
well as $|V(P_{y,z})\setminus\\{x\\}|<|V(P_{y,z})|\leq 3k+1$ and
$V(P_{u,x})\cap(V(P_{y,z})\setminus\\{x\\})=\emptyset$. ∎

We proceed to classify the edges of any $(s,t)$-path as good or bad (see
Figure 3). Intuitively, an edge is good if it corresponds to the first time
the path enters a layer $L_{i}$ for $i\leq dist(s,t)$.

Figure 3: An $(s,t)$-path where the good edges are colored blue and the bad
edges are colored red.

######  Definition 5.

Let $\hat{P}=u_{1},u_{2},\ldots u_{q}$ be any arbitrary $(s,t)$-path in $G$.
An edge $(u_{i},u_{i+1})$ of $\hat{P}$, with $1\leq i\leq q-1$, is good if
$i+1$ is the smallest integer in $[q]$ such that $u_{i+1}\in L_{j}$ for some
layer $L_{j}$ with $1\leq j\leq dist_{G}(s,t)$; else $(u_{i},u_{i+1})$ is bad.

In particular, the edges of any solution path can be partitioned into good
edges and bad edges. Intuitively, the good edges can be viewed as the edges
between consecutive layers $L_{i}$ and $L_{i+1}$, with $i<dist_{G}(s,t)$, that
contribute to the distance metric $dist_{G}(s,t)$. We have the following
observation.

######  Observation 5.

If an $(s,t)$-path $\hat{P}$ has at least $k$ bad edges, then its length is at
least $dist_{G}(s,t)+k$.

###### Proof.

Let $E(\hat{P})=E_{1}\cup E_{2}$ where $E_{1}$ and $E_{2}$ are the sets of
good and bad edges of $\hat{P}$, respectively. We have $|E_{2}|>k$. By the
definition of good edges, there is at least one good edge $(u,v)\in
E(\hat{P})$ where $v\in L_{j}$ for each $1\leq j\leq dist_{G}(s,t)$. Hence we
have $|E_{1}|\geq dist_{G}(s,t)$. Therefore, the length of $\hat{P}$, being
$|E_{1}|+|E_{2}|$, is at least $dist_{G}(s,t)+k$. ∎

Intuitively, the following lemma states that the intersection between the
subpath $P_{v,t}$ and any path from $u$ to $x$ of length at most $k$, must
belong to $P_{v,z}$ entirely.

######  Lemma 3.

Let $P,u,v,x$ and $z$ be as defined in Definitions 3 and 4. Let $P^{\prime}$
be a path of length at most $k$ from $u$ to $x$ in the graph $G[\bigcup_{i\geq
p}L_{i}]$. Then, the subpath $P_{v,z}$ contains all the vertices of $P_{v,t}$
that belong to $P^{\prime}$.

###### Proof.

Let $\mathcal{L}^{\prime}$ be the set of layers that contain at least one
vertex in $P^{\prime}$. Since the path $P^{\prime}$ is of length at most $k$,
$\mathcal{L}^{\prime}\subseteq\\{L_{i}:p\leq i\leq p+k\\}$. If the subpath
$P_{v,t}$ has length at most $2k$, then we are done as $P_{v,z}=P_{v,t}$.
Hence, we now suppose that the subpath $P_{v,z}$ of $P_{v,t}$ is of length
$2k$. Targeting a contradiction, suppose that $P_{v,t}$ contains a vertex
$w\notin V(P_{v,z})$ but $w\in V(P^{\prime})$. Thus $w$ is contained in a
layer in $\mathcal{L}^{\prime}$. Choose such a $w$ that is at the closest
distance to $v$ in $G$. Since $\mathcal{L}^{\prime}\subseteq\\{L_{i}:p\leq
i\leq p+k\\}$, $w$ belongs to a layer $L_{p+j_{1}}$ with $0\leq j_{1}\leq k$.

We now show that $P_{v,t}$ contains at least $k$ bad edges. Let $j_{2}$ be the
largest integer such that $L_{p+j_{2}}$ contains a vertex in $P_{v,z}$.
Finally, let $t\in L_{p+j_{3}}$ for $j_{3}\geq 0$ (see Figure 4 ).

$(a)$
$(b)$

Figure 4: $j_{1}$, $j_{2}$ and $j_{3}$ with the bad edges of $P_{v,t}$ colored
in red.

Consider the following cases.

Case $j_{3}\geq j_{2}$ (See Figure 4 (a)): We first show that there are
$2k-j_{2}$ bad edges of $P_{v,t}$ in the subpath $P_{v,z}$. Since $j_{2}$ is
the largest integer such that $L_{p+j_{2}}$ contains a vertex in $P_{v,z}$,
all the vertices of $P_{v,z}$ are contained within the set of layers
$\\{L_{i}:p\leq i\leq p+j_{2}\\}$. Recall that an edge is good if its tail
vertex corresponds to the first time the path $P_{v,t}$ enters a layer $L_{i}$
where $i\leq dist(s,t)=p+j_{3}$. At most $j_{2}$ of the edges of $P_{v,z}$ are
good with its tail vertices corresponding to the first time the path enters a
layer $L_{i},p+1\leq i\leq p+j_{2}$. Thus $|P_{v,z}|-j_{2}=2k-j_{2}$ edges of
$P_{v,t}$ are bad edges.

Let us look at the case when $j_{2}\leq j_{1}$. In this case, we have at least
$2k-j_{2}\geq 2k-j_{1}\geq 2k-k=k$ bad edges in the subpath $P_{v,t}$ as
$j_{1}\leq k$.

We now show that when $j_{2}>j_{1}$, there are $j_{2}-j_{1}$ bad edges of
$P_{v,t}$ in the subpath $P_{w,t}$, which is disjoint from $P_{v,z}$. Since
$w\in L_{p+j_{1}}$, $t\in L_{p+j_{3}}$ and $j_{3}\geq j_{2}$, there is a
prefix of the path $P_{w,t}$ from $w$ to a vertex in $L_{p+j_{2}}$ with all
the vertices of the path within the layers $L_{i}$ with $p+j_{1}\leq i\leq
p+j_{2}$. All the edges of this prefix path are bad as the path $P_{v,t}$ has
already visited these layers earlier in the subpath $P_{v,z}$.

Hence, overall, we have $2k-j_{2}+j_{2}-j_{1}=2k-j_{1}\geq 2k-k=k$ bad edges
in the subpath $P_{v,t}$ as $j_{1}\leq k$.

Case $j_{3}<j_{2}$ (See Figure 4 (b)): Similarly to the previous case, we
first show that there are $2k-j_{3}$ bad edges of $P_{v,t}$ in the subpath
$P_{v,z}$. Recall that an edge is good if its tail vertex corresponds to the
first time the path $P_{v,t}$ enters a layer $L_{i}$ where $i\leq
dist(s,t)=p+j_{3}$. At most $j_{3}$ of the edges of $P_{v,z}$ are good with
their tail vertices corresponding to the first time the path enters a layer
$L_{i},p+1\leq i\leq p+j_{3}$. Thus $|P_{v,z}|-j_{3}=2k-j_{3}$ edges of
$P_{v,t}$ are bad edges.

Let us look at the case when $j_{3}\leq j_{1}$. In this case, we have at least
$2k-j_{3}\geq 2k-j_{3}\geq 2k-k=k$ bad edges in the subpath $P_{v,t}$ as
$j_{1}\leq k$.

We now look at the case when $j_{3}>j_{1}$. Since $w\in L_{p+j_{1}}$ and $t\in
L_{p+j_{3}}$, there are at least $j_{3}-j_{1}$ edges in the subpath $P_{w,t}$.
Since $P_{v,z}$ has already visited the layers $L_{i}$ with $p+j_{1}\leq i\leq
p+j_{3}<p+j_{2}$, all the edges of $P_{w,t}$ are bad. Overall, we have
$2k-j_{3}+j_{3}-j_{1}=2k-j_{1}\geq 2k-k=k$ bad edges in the subpath $P_{v,t}$
as $j_{1}\leq k$.

####

In both cases, we conclude that there are at least $k$ bad edges in the
subpath $P_{v,t}$. Hence, from Observation 5, any path formed by concatenating
a shortest $(s,v)$-path with $P_{v,t}$ is of length at least
$dist_{G}(s,t)+k$. This path is shorter than $P$ as there is at least one edge
in the subpath $P_{u,v}$. This contradicts that $P$ is a shortest solution
path (as defined in Definition 3). ∎

The following lemma shows that the subpath $P_{x,y}$ does not intersect any
path from $u$ to $x$ of length at most $k$, except for at the vertex $x$.

######  Lemma 4.

Let $P,u,v,x,y$ and $z$ be as defined in Definitions 3 and 4. Any path
$P^{\prime}$ from $u$ to $x$ of size at most $k$ in the graph
$G[\bigcup_{i\geq p}L_{i}]$ that is disjoint from $P_{y,z}$ is disjoint from
$P_{x,v}$, except for at the vertex $x$.

###### Proof.

Suppose not. Then, let $w$ be the vertex in $P_{x,v}$ that is closest to $x$
and is contained in $P^{\prime}$. Consider the walk $W$ from $s$ to $t$
defined by $P_{s,u}\circ P^{\prime}_{u,w}\circ P_{w,y}\circ P_{y,v}\circ
P_{v,t}$. If $k^{\prime}<k$, we have $x=y$, and the claim follows as
$P_{x,v}=P_{y,v}$. Hence $|P_{y,v}|=k$. Note that
$|P_{s,u}|=|P_{s,v}|=dist_{G}(s,v)$ as $u,v\in L_{p}$. So, we have
$|P_{s,u}|+|P_{y,v}|+|P_{v,t}|\geq
dist_{G}(s,v)+k+dist_{G}(v,t)=dist_{G}(s,t)+k$ as $u,v\in L_{p}$. The walk $W$
contains the subpaths $P_{s,u}$, $P_{y,v}$ and $P_{v,t}$ which are vertex
disjoint except the vertex $v$ which is the last vertex of $P_{y,v}$ and the
first vertex of $P_{v,t}$. Since $P^{\prime}_{u,w}$ is disjoint from
$P_{v,z}$, by Lemma 3, it is disjoint from $P_{v,t}$. Thus any cycle in the
walk $W$ is contained in the sequence $P^{\prime}_{u,w}\circ P_{w,y}$. Thus,
the edges of the paths $P_{s,u}$, $P_{y,v}$ and $P_{v,t}$ are not part of any
cycles in the walk $W$. Hence, $W$ contains a path $\hat{P}$ of length that at
least the sum of these paths which is at least $dist_{G}(s,t)+k$. Note that
the path $\hat{P}$ is strictly shorter than $P$ as
$|P^{\prime}_{u,w}|<|P^{\prime}|\leq k=|P_{u,x}|$. This contradicts that $P$
is the shortest solution path as defined in Definition 3. ∎

We have the following corollary from Lemmas 3 and 4.

######  Corollary 1.

Let $P,u,v,x$ and $z$ be as defined in Definitions 3 and 4. Any path
$P^{\prime}$ from $u$ to $x$ of size at most $k$ that is disjoint from
$P_{y,z}$ is disjoint from the subpath $P_{x,t}$ of $P$.

###### Proof.

From Lemma 3, we can conclude that $P^{\prime}$ is disjoint from $P_{v,t}$ as
it is disjoint from $P_{v,z}$. From Lemma 4, we can conclude that $P^{\prime}$
is disjoint from $P_{x,v}$, except for at the vertex $x$. Thus, the corollary
follows. ∎

We now prove that Steps 8-15 of the algorithm are correct using the following
definition and lemma. First, identify some paths between pairs of vertices in
$u,v,x,y,z$ (see Figure 5).

Figure 5: The solution path corresponding to the algorithm in Steps 8-15.

######  Definition 6.

Let $P,u,v,x,y,z$ be as defined in Definitions 3 and 4. Let $P_{1}$ be an
arbitrary shortest $(s,u)$-path. Let $P_{2}$ be a path from $u$ to $x$ of
length $k$ that is disjoint from $P_{y,z}$. Let $P_{3}$ and $P_{4}$ be
internally vertex disjoint paths from $x$ to $v$ and $v$ to $t$, respectively,
in the graph $G-(V(P_{1})\cup V(P_{2})\setminus\\{x\\})$.

We now show that the concatenation of the paths defined above results in a
solution path.

######  Lemma 5.

The path $P^{\prime}=P_{1}\circ P_{2}\circ P_{3}\circ P_{4}$ is a path of
length at least $dist_{G}(s,t)+k$.

###### Proof.

The paths $P_{3}$ and $P_{4}$ are vertex disjoint from each other and are
vertex disjoint from $P_{1}$ and $P_{2}$ by definition. The vertex set of the
path $P_{1}$ is contained in $\bigcup_{i\in[p]}L_{i}$ with only the last
vertex $u$ belonging to layer $L_{p}$. Also, the path $P_{2}$ is contained in
$\bigcup_{i\geq p}L_{i}$. Hence, $P_{1}$ and $P_{2}$ are internally vertex
disjoint as well. We can thus conclude that $P^{\prime}$ is a path, and that
$|P^{\prime}|=|P_{1}|+|P_{2}|+|P_{3}|+|P_{4}|\geq
dist_{G}(s,u)+k+|P_{3}|+dist_{G}(v,t)\geq
dist_{G}(s,u)+k+dist_{G}(u,t)=dist_{G}(s,t)+k$. ∎

Finally, we prove the correctness of Steps 6-15 of the algorithm by showing
that the algorithm indeed computes a collection of paths as defined in
Definition 3.

######  Lemma 6.

Steps 6-15 of Algorithm 1 are correct.

###### Proof.

We first show that if the instance is a YES-instance, then the algorithm
returns YES. Let $P$ be a shortest solution path. In one of the iterations
from Step 9, the algorithm considers $p,u,v,x$ as defined in Definitions 3 and
4. In Step 10, the algorithm computes a shortest $(s,u)$-path $P_{1}$ via BFS.
Such a path exists as $P_{s,u}$ is a candidate. In Step 11, it computes a
$(u,x)$-path $P_{2}$ of length $k$ in the graph $G[F]$ for each
$F\in{\mathcal{F}}$. From Observation 4, there exists $F\in{\mathcal{F}}$ such
that $V(P_{u,x})\subseteq F$ and $V(P_{y,z})\cap F=\emptyset$ when $y\neq x$.
Also, from the same observation, when

if $y=x$, there exists $F\in{\mathcal{F}}$ such that $V(P_{u,x})\subseteq F$
and $(V(P_{y,z})\setminus\\{x\\})\cap F=\emptyset$. Then the algorithm will
compute $P_{2}$ as $P_{u,x}$ is a candidate. In Step 12, the algorithm
computes two vertex disjoint paths, $P_{3}$ from $x$ to $v$ and $P_{4}$ from
$v$ to $t$ in the graph $G-(V(P_{1})\cup V(P_{2})\setminus\\{x\\})$. The paths
$P_{x,v}$ and $P_{v,t}$ are disjoint from $P_{1}$ as $P_{1}$ is contained in
layers $L_{i}$ with $1\leq i\leq p$ (except $u\in L_{p}$) and $P_{x,v}$ and
$P_{v,t}$ are contained in layers $L_{i}$ with $i\geq p$. The paths $P_{x,v}$
and $P_{v,t}$ are disjoint from $P_{2}$ (except the vertex $x$) from Corollary
1 as $P_{2}$ is disjoint from $P_{y,z}$. Thus, paths $P_{3}$ and $P_{4}$ exist
as $P_{x,v}$ and $P_{v,t}$ are candidates. Hence, the algorithm correctly
returns YES in Step 12.

We now show that if the algorithm returns YES in Step 12, then the instance is
a YES-instance. The algorithm returns YES only when it finds a shortest
$(s,u)$-path $P_{1}$, a path $P_{2}$ in graph $G[F]$ for some
$F\in{\mathcal{F}}$ and two vertex disjoint paths $P_{3}$ and $P_{4}$, one
from $x$ to $v$ and other from $v$ to $t$ in the graph $G-(V(P_{1})\cup
V(P_{2})\setminus\\{x\\})$. Notice that the paths $P_{1},P_{2},P_{3}$ and
$P_{4}$ satisfy the conditions in Definition 6. From Lemma 5, we can conclude
that the concatenation of these paths is a solution path as its length is at
least $dist_{G}(s,t)+k$. Hence, the instance is a YES-instance. ∎

###  3.3 Running Time

######  Lemma 7.

Algorithm 1 runs in $46.308^{k}n^{{\mathcal{O}}(1)}$ time.

###### Proof.

Step 1 of the algorithm can be done by a BFS, which takes ${\mathcal{O}}(n+m)$
time. In Steps 3-5, we use Theorem 3, which takes
$6.745^{2k-1}n^{{\mathcal{O}}(1)}\leq 45.495^{k}n^{{\mathcal{O}}(1)}$ time.
The BFS in Step 6 takes ${\mathcal{O}}(n+m)$ time. Afterwards, Step 7 takes
${4k+2\choose k+1}\cdot 2^{o(4k+2)}\cdot n\log n$ time as per Lemma 1, which
is ${4k\choose k}2^{o(k)}n^{2}$ time. We have

$\displaystyle{4k\choose k}$ $\displaystyle=$
$\displaystyle\frac{4k!}{k!(4k-k)!}$ $\displaystyle\leq$
$\displaystyle\frac{e^{1/12(4k)}\sqrt{2\pi(4k)}((4k)/e)^{4k}}{\sqrt{2\pi
k}(k/e)^{k}\sqrt{2\pi(3k)}(3k)/e)^{3k}}$ $\displaystyle=$
$\displaystyle\frac{e^{1/12(4k)}\sqrt{4k}}{\sqrt{2\pi
k(3k)}}\left(\frac{(4k)/e}{k/e}\right)^{k}\left(\frac{(4k)/e}{(3k)/e}\right)^{3k}$
$\displaystyle\leq$ $\displaystyle\frac{e^{1/12(4k)}\sqrt{4k}}{\sqrt{2\pi
k(3k)}}4^{k}\left(\frac{4}{3}\right)^{3k}$ $\displaystyle\leq$
$\displaystyle\left(\frac{256}{27}\right)^{k}$

using the Stirling’s approximation inequality $n!\leq e^{1/12n}\sqrt{2\pi
n}(n/e)^{n}$ where $e$ is Euler’s constant. Thus the time taken by Step 7 is
$(256/27)^{k}2^{o(k)}n^{2}$. The size of the $(n,k+1,3k+1)$-lopsided universal
family ${\mathcal{F}}$ is bounded by ${4k+2\choose k+1}\cdot
2^{o(4k+2)}\cdot\log n$, which is $(256/27)^{k}2^{o(k)}n$. The number of
iterations in Steps 8-15 is thus $(256/27)^{k}2^{o(k)}n\cdot rn^{3}$. The
shortest $(s,u)$-path in Step 10 can be computed in linear time. The path
$P_{2}$ of size $k$ is computed via the algorithm in Theorem 1, which takes
$4.884^{k}n^{{\mathcal{O}}(1)}$ time. The two disjoint paths in Step 12 are
computed by the $2$-Disjoint Paths algorithm on class $\mathcal{C}$, which we
assume to run in polynomial time. Overall, the time spent in Steps 8-15 is
$(256/27)^{k}\cdot 4.884^{k}2^{o(k)}n^{{\mathcal{O}}(1)})\leq
46.308^{k}n^{{\mathcal{O}}(1)}$. So, the total running time is
$46.308^{k}n^{{\mathcal{O}}(1)}$. ∎

We thus have the following theorem, whose proof follows from Observation 1,
Lemma 6 and Lemma 7.

######  Theorem 4.

Let $\mathcal{C}$ be a class of graphs where $2$-Disjoint Paths can be solved
in polynomial time. Then, Longest $(s,t)$-Detour on $\mathcal{C}$ can be
solved in $46.308^{k}n^{{\mathcal{O}}(1)}$ time.

## References

  * [1] Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo.  Solving max-r-sat above a tight lower bound.  Algorithmica, 61(3):638–655, 2011.
  * [2] Noga Alon, Raphael Yuster, and Uri Zwick.  Color-coding.  Journal of the ACM (JACM), 42(4):844–856, 1995.
  * [3] Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V Fomin.  Finding detours is fixed-parameter tractable.  In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017\.
  * [4] Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk.  On multiway cut parameterized above lower bounds.  ACM Transactions on Computation Theory (TOCT), 5(1):1–11, 2013\.
  * [5] Reinhard Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [6] Gabriel Andrew Dirac.  Some theorems on abstract graphs.  Proceedings of the London Mathematical Society, 3(1):69–81, 1952\.
  * [7] Fedor V Fomin, Petr A Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh.  Detours in directed graphs.  In 39th International Symposium on Theoretical Aspects of Computer Science, 2022.
  * [8] Fedor V Fomin, Petr A Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Going far from degeneracy.  SIAM Journal on Discrete Mathematics, 34(3):1587–1601, 2020.
  * [9] Fedor V Fomin, Petr A Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Parameterization above a multiplicative guarantee.  In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [10] Fedor V Fomin, Petr A Golovach, Danil Sagunov, and Kirill Simonov.  Algorithmic extensions of dirac’s theorem.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 406–416. SIAM, 2022.
  * [11] Fedor V Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.  Efficient computation of representative families with applications in parameterized and exact algorithms.  Journal of the ACM (JACM), 63(4):29, 2016.
  * [12] Fedor V Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Long directed (s, t)-path: Fpt algorithm.  Information Processing Letters, 140:8–12, 2018.
  * [13] Gregory Gutin, Eun Jung Kim, Michael Lampis, and Valia Mitsou.  Vertex cover problem parameterized above and below tight bounds.  Theory of Computing Systems, 48(2):402–410, 2011.
  * [14] Gregory Gutin and Matthias Mnich.  A survey on graph problems parameterized above and below guaranteed values.  arXiv preprint arXiv:2207.12278, 2022.
  * [15] Meike Hatzel, Konrad Majewski, Michał Pilipczuk, and Marek Sokołowski.  Simpler and faster algorithms for detours in planar digraphs.  arXiv preprint arXiv:2301.02421, 2023.
  * [16] Bart MP Jansen, László Kozma, and Jesper Nederlof.  Hamiltonicity below dirac’s condition.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 27–39. Springer, 2019.
  * [17] Ioannis Koutis.  Faster algebraic algorithms for path and packing problems.  In International Colloquium on Automata, Languages, and Programming, pages 575–586. Springer, 2008.
  * [18] Ioannis Koutis and Ryan Williams.  Algebraic fingerprints for faster algorithms.  Communications of the ACM, 59(1):98–105, 2015.
  * [19] Daniel Lokshtanov, NS Narayanaswamy, Venkatesh Raman, MS Ramanujan, and Saket Saurabh.  Faster parameterized algorithms using linear programming.  ACM Transactions on Algorithms (TALG), 11(2):1–31, 2014.
  * [20] Meena Mahajan and Venkatesh Raman.  Parameterizing above guaranteed values: Maxsat and maxcut.  Journal of Algorithms, 31(2):335–354, 1999.
  * [21] Moni Naor, Leonard J Schulman, and Aravind Srinivasan.  Splitters and near-optimal derandomization.  In focs, page 182. IEEE, 1995.
  * [22] Ryan Williams.  Finding paths of length k in ${O^{*}(2^{k})}$ time.  Information Processing Letters, 109(6):315–318, 2009.