Finding common ancestors and disjoint paths in DAGs
David Eppstein · eScholarship (California Digital Library) · 1995
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) or O(mn d-1 ). 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. # Work supported in part by NSF grant CCR-9258355 and by matching funds from Xerox Corp. 1 Introduction We are interested in two problems in directed acyclic graphs (DAGs), both involving pairs of vertex-disjoint paths. In the first problem, we are given two nodes in the DAG, and we wish ...