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.