Route existence between n pairs of nodes 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.
As Chandra Chekuri pointed out in a comment, you could just compute the transitive closure via fast matrix multiplication, solving the problem in O($n^\omega$) time (use your favorite method, O($n^{2.376}$) via Coppersmith and Winograd, or more practically using Strassen's O($n^{2.81}$)), and this would be good for dense graphs.

Now, I claim that if you can beat this running time for your problem for dense graphs, you would obtain an algorithm for triangle detection which is more efficient than computing the product of two Boolean matrices. The existence of such an algorithm is a major open problem.

I'll reduce the triangle problem to the n-pairs-DAG-reachability problem.
Suppose we are given a graph G on n nodes and we want to determine whether G contains a triangle. 

Now, from G create a DAG G' as follows. Create four copies of the vertex set, $V_1$, $V_2$, $V_3$, $V_4$. For copies $u_i\in V_i$, $v_{i+1}\in V_{i+1}$ for $i=1,2,3$, add an edge $(u_i,v_{i+1})$ iff $(u,v)$ was in G.  Now if we ask whether there is a path between any of the pairs $(u_1, u_4)$ for all $u\in $G, then this would exactly be asking whether there is a triangle in $G$. The current graph has $4n$ nodes and we are asking about $n$ pairs. However, we can add $2n$ isolated dummy nodes and have $3n$ queries instead (by adding a query for $2n$ distinct pairs $(y,d)$ where $y\in V_2\cup V_3$ and $d$ a dummy), thus obtaining a $6n$-node instance of exactly your problem.