# 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.

• It is not entirely clear what you are asking. Are you looking for a single path containing the edges you mention? Or are you looking for multiple paths? Feb 9 '11 at 16:12
• @Dave: He's looking for the OR of a small piece of the transitive closure matrix. Feb 9 '11 at 16:37
• @Alexandru, 1->4, 2->3. You add 3->1, 4->2. Feb 9 '11 at 16:41
• You can compute the transitive closure via fast matrix multiplication which would be better than the O(nm) time if m is large. Feb 10 '11 at 18:04
• @alexandru: that's not what your question asked though, to be fair. You were asking for a faster bound, not practical implementations (which is a valid, but separate question) Feb 13 '11 at 16:13

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.

Topological sort ($O(m+n)$) then work down it propagating a bitset of nodes from which each node can be reached ($O(m n)$).

After the topological sort you can do a $O(n)$ quick-rejection (if node $n+x$ comes before node $x$ in the sort then there's no path from $x$ to $n+x$).

• This does not really seem to be faster to me. If $m=o(n)$, then the algorithm of the question could just do a simple preprocessing answering NO if there is an isolated vertex. Feb 9 '11 at 16:32
• How is this better then my basic algorithm? Feb 9 '11 at 16:32
• @Alexandru, I think it's somewhat better because it packs bits. That is, it's $O((m+n)n/w)$ where $w$ is the word width. It's not clear if you care for such improvements. Feb 9 '11 at 16:45
• It is a trade off: you use O(n*n/w) extra memory instead of O(n). Feb 9 '11 at 17:19
• @Alexandru, asymptotically in the worst case it's the same, but the average-case analysis is tricky, and which is better might depend on the statistics of expected graph structure. Feb 9 '11 at 17:23

If you want to keep memory low (avoid $O(N^2)$ matrix), you can add some heuristics:

yespath = array(1..N)       // output of the algorithm
// initially filled with false
processed = array(1..N)     // processed nodes

// HEURISTIC 1: some preprocessing
for every node u in 1..N
if (no outbound edges from u) then processed[u] = true
if (no inbound edges to u+N) then processed[u] = true

for each node u in [1..N]    // MAIN loop
if (not processed[u]) then
collected = [u]          // a list that initially contains u
visited = array(1..2*N)  // filled with zeroes
do a breadth first scan from u
for each node v found in the search
set visited[v] = distance from u
if (v <= N) then add v to collected
end do

// HEURISTIC 2: useful collected info on other nodes <= N
foreach node v in collected
processed[v] = true
if ( visited[ v + N ] > 0 and visited[v] < visited[v+N] ) then yespath[v] = true
end foreach

end if
end for // MAIN loop


HEURISTIC 3
Instead of using a matrix of size $O(N^2)$, you can use a buffer (simple array or hash table) of the k-previous scans (size $O(N*k)$) that contains a node $e > u + N$ (u is the current node in main loop), and during breadth-first check if we reach a node contained in a previous buffered path.

Other heuristics can be added, but their efficiency (and efficiency of the three proposed) highly depends on graph structure.