Donald Bren School of Information and Computer Sciences

We consider the problem of finding pairs of vertex-disjoint paths in a DAG, either connecting two given nodes to a common ancestor, or connecting two given pairs of terminals. It was known how to find a single pair of paths, for either type of input, in polynomial time. We show how to find the k pairs with shortest combined length, in time O(mn + k). We also show how to count all such pairs of paths in O(mn) arithmetic operations. These results can be extended to finding or counting tuples of d disjoint paths, in time O(mn^(d-1 + k). We give further results on finding the subset of the DAG involved in pairs of disjoint paths, and on finding disjoint paths in linear space.