Given a directed acyclic graph with $2n$ nodes how can one determine if there is a path between any of following n pairs of nodes $(1 \rightarrow n+1), \ldots, (n \rightarrow n+n)$? There is a simple algorithm in $O(n \cdot (n + m))$ (where m is the number of edges) by doing a search from each node $1 \ldots n$, but can it be done better?EDIT: I'm looking for existence, not complete paths.
Route existence between n pairs of nodes
ds.algorithms;graph algorithms;directed acyclic graph