Linear time algorithms for two disjoint paths problems on directed acyclic graphs

We present an algorithm that, given two vertices s1 and s2 of a directed acyclic graph, constructs in linear time a data structure using linear space that, for each pair (u,v) of two vertices u and v, in constant time can output a tuple (s1,t1,s2,t2) with {t1,t2}={u,v} such that there are two disjoint paths p1, from s1 to t1, and p2, from s2 to t2, if such a tuple exists. The data structure is simpler than such a data structure for general directed graphs that can be obtained from results of Georgiadis and Tarjan. Disjoint can mean vertex- as well as edge-disjoint. As an application and main result we show that the data structure can be used to solve the 2-disjoint paths problem on directed acyclic graphs optimally, i.e., in linear time.