Join-Reachability Problems in Directed Graphs

For a given collection (mathcal{G}) of directed graphs we define the join-reachability graph of (mathcal{G}) , denoted by (mathcal{J}(mathcal{G})) , as the directed graph that, for any pair of vertices u and v, contains a path from u to v if and only if such a path exists in all graphs of  (mathcal{G}) . Our goal is to compute an efficient representation of  (mathcal{J}(mathcal{G})) . In particular, we consider two versions of this problem. In the explicit version we wish to construct the smallest join-reachability graph for  (mathcal{G}) . In the implicit version we wish to build an efficient data structure, in terms of space and query time, such that we can report fast the set of vertices that reach a query vertex in all graphs of  (mathcal{G}) . This problem is related to the well-studied reachability problem and is motivated by emerging applications of graph-structured databases and graph algorithms. We consider the construction of join-reachability structures for two graphs and develop techniques that can be applied to both the explicit and the implicit problems. First we present optimal and near-optimal structures for paths and trees. Then, based on these results, we provide efficient structures for planar graphs and general directed graphs.