An efficient algorithm for answering graph reachability queries

Given a directed graph G, to check whether a node v is reachable from another node u through a path is often required. In a database system, such an operation is called a recursion computation or reachability checking and not efficiently supported. The reason for this is that the space to store the whole transitive closure of G is prohibitively high. In this paper, we address this issue and propose an O(n(2) + bn root b) time algorithm to decompose a directed acyclic graph (DAG) into a minimized set of disjoint chains to facilitate reachability checking, where n is the number of the nodes and b is the DAG's width, defined to be the size of a largest node subset U of the DAG such that for every pair of nodes u, v epsilon U, there does not exist a path from u to v or from v to u. Using this algorithm, we are able to label a graph in O(be) time and store all the labels in O(bn) space with O(logb) reachability checking time, where e is the number of the edges of the DAG The method can also be extended to handle cyclic directed graphs. Experiments have been performed, showing that our method is promising.