Given four distinct vertices s
1,s
2,t
1, and t
2 of a graph G, the 2-disjoint paths problem is to determine two disjoint paths, p
1 from s
1 to t
1 and p
2 from s
2 to t
2, if such paths exist. Disjoint can mean vertex- or edge-disjoint.
Both, the edge- and the vertex-disjoint version of the problem, are
NP\mathcal{NP}-hard in the case of directed graphs. For undirected graphs, we show that the
O(
mn)-time algorithm of Shiloach can be modified so as to solve the 2-(vertex-)disjoint paths problem in
O(
n+
mα(
m,
n)) time, where
m is the number of edges in
G,
n is the number of vertices in
G, and
α denotes the inverse of the Ackermann function. Our result also improves the running time for the 2-edge-disjoint paths problem
on undirected graphs as well as the running times for the decision versions of the 2-vertex- and the 2-edge-disjoint paths
problem on dags.