Institution: Stanford University, Department of Computer Science

Title: The two paths problem is polynomial

Author: Shiloach, Yossi

Date: April 1978

Abstract: Given an undirected graph G = (V,E) and vertices $s_1$,$t_1$;$s_2$,$t_2$, the problem is to determine whether or not G admits two vertex disjoint paths $P_1$ and $P_2$, connecting $s_1$ with $t_1$ and $s_2$ with $t_2$ respectively. This problem is solved by an O($n\cdot m$) algorithm (n = |V|, m = |E|). An important by-product of the paper is a theorem that states that if G is 4-connected and non-planar, then such paths $P_1$ and $P_2$ exist for any choice of $s_1$, $s_2$, $t_1$, and $t_2$, (as was conjectured by Watkins [1968]).

http://i.stanford.edu/pub/cstr/reports/cs/tr/78/654/CS-TR-78-654.pdf