Finding Disjoint Paths on Directed Acyclic Graphs

摘要

Given k + 1 pairs of vertices (s_1, s_2), (u_1, υ_1), ... , (u_k, υ_k) of a directed acyclic graph, we show that a modified version of a data structure of Suurballe and Tarjan can output, for each pair (u_l, υ_l) with 1 ≤ l ≤ k, a tuple (s_1, t_1, s_2, t_2) with {t_1, t_2} = {u_l, υ_l} in constant time such that there are two disjoint paths p_1, from s_1 to t_1, and p_2, from s_2 to t_2, if such a tuple exists. Disjoint can mean vertex- as well as edge-disjoint. As an application we show that the presented data structure can be used to improve the previous best known running time O(mn) for the so called 2-disjoint paths problem on directed acyclic graphs to O(m(log_(2+m)n) log~3 n). In this problem, given a tuple (s_1, s_2, t_1, t_2) of four vertices, we want to construct two disjoint paths p_1, from s_1 to t_1, and p_2, from s_2 to t_2, if such paths exist.