<p>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.</p>

<p>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.</p>

<p>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. </p>

<p>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.</p>

CC BY-SA 2.5
2011-03-23T18:09:59.843Z
2011-03-23T18:09:59.843Z
virgi
<p>If you want to keep memory low (avoid $O(N^2)$ matrix), you can add some heuristics:</p>

<pre><code>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 &lt;= N) then add v to collected
    end do

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

  end if
end for // MAIN loop
</code></pre>

<p>HEURISTIC 3<br>
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 &gt; 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.</p>

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

CC BY-SA 2.5
2011-02-18T12:07:33.413Z
2011-02-18T12:07:33.413Z
Marzio De Biasi
<p>Topological sort ($O(m+n)$) then work down it propagating a bitset of nodes from which each node can be reached ($O(m n)$).</p>

<p>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$).</p>

CC BY-SA 2.5
2011-02-09T16:32:28.567Z
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.
Serge Gaspers
CC BY-SA 2.5
2011-02-09T16:32:30.273Z
How is this better then my basic algorithm?
Alexandru
CC BY-SA 2.5
2011-02-09T16:45:19.707Z
@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.
Radu GRIGore
CC BY-SA 2.5
2011-02-09T17:19:42.873Z
It is a trade off: you use O(n*n/w) extra memory instead of O(n).
Alexandru
CC BY-SA 2.5
2011-02-09T17:23:35.930Z
@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.
Peter Taylor
CC BY-SA 2.5
2011-02-09T15:42:07.860Z
2011-02-09T17:18:25.500Z
2011-02-09T17:18:25.500Z
Peter Taylor
<p>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?</p>

<p>EDIT: I'm looking for existence, not complete paths.</p>

CC BY-SA 2.5
2011-02-09T16:12:05.623Z
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?
Dave Clarke
CC BY-SA 2.5
2011-02-09T16:31:33.003Z
@Dave: multiple paths.
Alexandru
CC BY-SA 2.5
2011-02-09T16:33:58.477Z
My current idea is to add the reverse edges (n+1 -> 1) .. (n+n -> n) and find cycles (strongly connected components) in the resulted digraph. I'm not sure if it works, but this would be O(n+m).
Alexandru
CC BY-SA 2.5
2011-02-09T16:37:53.307Z
@Dave: He's looking for the OR of a small piece of the transitive closure matrix.
Radu GRIGore
CC BY-SA 2.5
2011-02-09T16:39:15.753Z
@Serge: See edit. I don't care about the paths. Only if they exist.
Alexandru
CC BY-SA 2.5
2011-02-09T16:41:40.820Z
@Alexandru, 1->4, 2->3. You add 3->1, 4->2.
Radu GRIGore
CC BY-SA 2.5
2011-02-10T18:04:41.470Z
You can compute the transitive closure via fast matrix multiplication which would be better than the O(nm) time if m is large.
Chandra Chekuri
CC BY-SA 2.5
2011-02-13T14:52:22.670Z
@Chandra Chekuri: You could write an answer with your idea and you would probably win the bounty.
Aaron Sterling
CC BY-SA 2.5
2011-02-13T15:47:16.740Z
@Chandra: My typical graphs have N ~= 40000 and M = N^1.1 ... N^1.3. Even if fast matrix multiplication is faster, the memory requirement is huge O(N^2).
Alexandru
CC BY-SA 2.5
2011-02-13T16:13:01.427Z
@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)
Suresh Venkat
CC BY-SA 2.5
2011-02-17T22:22:07.350Z
How is your graph represented [Adjacency matrix, list, etc]?
Foo Bah
CC BY-SA 2.5
2011-02-17T23:07:55.737Z
@Foo Bah: the graph is represented as a list
Alexandru
<ds.algorithms><graph-algorithms><directed-acyclic-graph>
Route existence between n pairs of nodes
Alexandru
# Route existence between n pairs of nodes

(Asked by: username_0 on 2011-02-09)

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.

**Tags:** ds.algorithms, graph-algorithms, directed-acyclic-graph

> **Comments:**
> **username_1**: 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?  
> **username_0**: @Dave: multiple paths.  
> **username_0**: My current idea is to add the reverse edges (n+1 -> 1) .. (n+n -> n) and find cycles (strongly connected components) in the resulted digraph. I'm not sure if it works, but this would be O(n+m).  
> **username_2**: @Dave: He's looking for the OR of a small piece of the transitive closure matrix.  
> **username_0**: @Serge: See edit. I don't care about the paths. Only if they exist.  
> **username_2**: @username_0, 1->4, 2->3. You add 3->1, 4->2.  
> **username_3**: You can compute the transitive closure via fast matrix multiplication which would be better than the O(nm) time if m is large.  
> **username_4**: @username_3: You could write an answer with your idea and you would probably win the bounty.  
> **username_0**: @Chandra: My typical graphs have N ~= 40000 and M = N^1.1 ... N^1.3. Even if fast matrix multiplication is faster, the memory requirement is huge O(N^2).  
> **username_5**: @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)  
> **username_6**: How is your graph represented [Adjacency matrix, list, etc]?  
> **username_0**: @username_6: the graph is represented as a list  

---

## 3 answers

### Answer by username_7 on 2011-03-23. Score: 5

As username_3 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.


---

### Answer by username_8 on 2011-02-18. Score: 0

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.


---

### Answer by username_9 on 2011-02-09. Score: 0

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$).

> **Comments:**
> **username_10**: 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.  
> **username_0**: How is this better then my basic algorithm?  
> **username_2**: @username_0, 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.  
> **username_0**: It is a trade off: you use O(n*n/w) extra memory instead of O(n).  
> **username_9**: @username_0, 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.  

---

