8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dave Clarke Feb 9 '11 at 16:12
  • 2
    $\begingroup$ @Dave: He's looking for the OR of a small piece of the transitive closure matrix. $\endgroup$ – Radu GRIGore Feb 9 '11 at 16:37
  • 1
    $\begingroup$ @Alexandru, 1->4, 2->3. You add 3->1, 4->2. $\endgroup$ – Radu GRIGore Feb 9 '11 at 16:41
  • 6
    $\begingroup$ You can compute the transitive closure via fast matrix multiplication which would be better than the O(nm) time if m is large. $\endgroup$ – Chandra Chekuri Feb 10 '11 at 18:04
  • 4
    $\begingroup$ @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) $\endgroup$ – Suresh Venkat Feb 13 '11 at 16:13
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Serge Gaspers Feb 9 '11 at 16:32
  • 1
    $\begingroup$ How is this better then my basic algorithm? $\endgroup$ – Alexandru Feb 9 '11 at 16:32
  • $\begingroup$ @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. $\endgroup$ – Radu GRIGore Feb 9 '11 at 16:45
  • $\begingroup$ It is a trade off: you use O(n*n/w) extra memory instead of O(n). $\endgroup$ – Alexandru Feb 9 '11 at 17:19
  • $\begingroup$ @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. $\endgroup$ – Peter Taylor Feb 9 '11 at 17:23
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.