On the connection between the undirected and the Acyclic Directed Two Disjoint Paths Problem

Given an undirected graph G and four distinct special vertices s(1),s(2),t(1),t(2), the Undirected Two Disjoint Paths Problem consists in determining whether there are two disjoint paths connecting s(1) to t(1) and s(2) to t(2), respectively. There is an analogous version of the problem for acyclic directed graphs, in which it is required that the two paths be directed, as well. The well known characterizations for the nonexistence of solutions in both problems are, in some sense, the same, which indicates that under some weak conditions the edge orientations in the directed version are irrelevant. We present the first direct proof of the irrelevance of edge orientations.4719120