Parametrized complexity of the 2-Long Paths Problem Consider the following problem:


  Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$ to $t$, each of length $\ge k$.


Is there an FPT time algorithm for the above problem?



The problem of a single long path is known to be FPT, and so is deciding whether there exists two paths of length exactly $k$ from $s$ to $t$.

What happen if we combine both?
Your problem is fixed-parameter tractable, which follows from the heavy machinery of Robertson &amp; Seymour. Your problem can be stated in terms of rooted minors. A graph $H$ with designated root vertices $s$ and $t$ is a rooted minor of a graph $G$ with roots $s$ and $t$, iff there is a function $f \colon V(H) \to 2^{V(G)}$ which assigns to each vertex of $H$ a subset of vertices in $G$, called a branch set, such that the following holds:


For each $v \in V(H)$ the branch set $f(v) \subseteq V(G)$ induced a connected subgraph of $G$, and
The sets $f(v)$ and $f(u)$ are disjoint for $u \neq v$, and
For each edge $e = \{u,v\} \in E(H)$, there is an edge of $G$ between the branch set $f(u)$ and the branch set $f(v)$, and 
The branch set of $s \in V(H)$ contains the $s$-vertex in $G$, and the branch set of $t \in V(H)$ contains the $t$-vertex in $G$.


Now consider the rooted graph $H$ with roots $s$ and $t$, connected by two vertex-disjoint paths of length $k$. (So $H$ is a cycle of length $2k$ with the root vertices at distance $k$ along the cycle.) You can show that $G$ has two vertex-disjoint $st$ paths of length at least $k$ if and only if the graph $G$ with roots $s$ and $t$ has $H$ as a rooted minor. Testing rooted minors is fixed-parameter tractable parameterized by the size of $H$, which follows from Graph Minors XIII. So your problem is FPT.

(If you are not familiar with graph minors, you might want to first absorb the fact that a graph has a cycle of length at least $k$ iff it contains the $k$-vertex cycle graph as a minor.)