## Abstract

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.

This is a preview of subscription content, access via your institution.

## Notes

- 1.
We caution the reader not to confuse the terms “unoriented” and “undirected”.

## References

- 1.
Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. In: SIGMOD’89: Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, pp. 253–262 (1989)

- 2.
Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput.

**1**(2), 131–137 (1972) - 3.
Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: FOCS’00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p. 198 (2000)

- 4.
Chazelle, B.: Filtering search: a new approach to query-answering. SIAM J. Comput.

**15**(3), 703–724 (1986) - 5.
Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: WWW’01: Proceedings of the 10th International Conference on World Wide Web, pp. 613–622 (2001)

- 6.
Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th ACM Symp. on Theory of Computing, pp. 135–143 (1984)

- 7.
Georgiadis, L.: Computing frequency dominators and related problems. In: ISAAC’08: Proceedings of the 19th International Symposium on Algorithms and Computation, pp. 704–715 (2008)

- 8.
Georgiadis, L.: Testing 2-vertex connectivity and computing pairs of vertex-disjoint

*s*–*t*paths in digraphs. In: Proc. 37th Int’l. Coll. on Automata, Languages, and Programming, pp. 738–749 (2010) - 9.
Georgiadis, L., Tarjan, R.E.: Dominator tree verification and vertex-disjoint paths. In: Proc. 16th ACM-SIAM Symp. on Discrete Algorithms, pp. 433–442 (2005)

- 10.
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput.

**13**(2), 338–355 (1984) - 11.
JaJa, J., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In: ISAAC’04: Proceedings of the 15th International Symposium on Algorithms and Computation, pp. 558–568 (2004)

- 12.
Kameda, T.: On the vector representation of the reachability in planar directed graphs. Inf. Process. Lett.

**3**(3), 75–77 (1975) - 13.
Katriel, I., Kutz, M., Skutella, M.: Reachability substitutes for planar digraphs. Technical report MPI-I-2005-1-002, Max-Planck-Institut Für Informatik, (2005)

- 14.
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.

**36**(2), 177–189 (1979) - 15.
Nardelli, E., Talamo, M., Vocca, P.: Efficient searching for multi-dimensional data made simple. In: Proc. 7th European Symposium on Algorithms, pp. 339–353 (1999)

- 16.
Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM

**29**(7), 669–679 (1986) - 17.
Talamo, M., Vocca, P.: Compact implicit representation of graphs. In: Proc. 24st Wks. on Graph-Theoretic Concepts in Computer Science, pp. 164–176 (1998)

- 18.
Talamo, M., Vocca, P.: An efficient data structure for lattice operations. SIAM J. Comput.

**28**(5), 1783–1805 (1999) - 19.
Tamassia, R., Tollis, I.G.: Dynamic reachability in planar digraphs with one source and one sink. Theor. Comput. Sci.

**119**(2), 331–343 (1993) - 20.
Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput.

**1**(2), 146–159 (1972) - 21.
Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM

**51**(6), 993–1024 (2004) - 22.
Wang, H., He, H., Yang, J., Yu, P.S., Yu, J.X.: Dual labeling: answering graph reachability queries in constant time. In: ICDE’06: Proceedings of the 22nd International Conference on Data Engineering, p. 75 (2006)

## Acknowledgements

We would like to thank Li Zhang for several useful discussions. We also thank the anonymous reviewers for helpful comments and suggestions.

## Author information

### Affiliations

### Corresponding author

## Additional information

This research project has been funded by the John S. Latsis Public Benefit Foundation. The sole responsibility for the content of this paper lies with its authors.

## Rights and permissions

## About this article

### Cite this article

Georgiadis, L., Nikolopoulos, S.D. & Palios, L. Join-Reachability Problems in Directed Graphs.
*Theory Comput Syst* **55, **347–379 (2014). https://doi.org/10.1007/s00224-013-9450-7

Published:

Issue Date:

### Keywords

- Algorithms
- Data structures
- Graph algorithms
- Reachability
- Combinatorial complexity