Document Open Access Logo

Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs

Authors Krishnendu Chatterjee, Rasmus Rasmus Ibsen-Jensen, Andreas Pavlogiannis

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.28.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Krishnendu Chatterjee
Rasmus Rasmus Ibsen-Jensen
Andreas Pavlogiannis

Cite As Get BibTex

Krishnendu Chatterjee, Rasmus Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.28

Abstract

We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-\epsilon} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity.

Subject Classification

Keywords
  • Graph algorithms
  • Constant-treewidth graphs
  • Reachability queries
  • Distance queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD'13, SIGMOD'13, pages 349-360, 2013. Google Scholar
  2. Takuya Akiba, Christian Sommer, and Ken-ichi Kawarabayashi. Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core. In EDBT, pages 144-155, 2012. Google Scholar
  3. Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees . Discrete Applied Mathematics, 23(1):11-24, 1989. Google Scholar
  4. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. In ICALP 13, pages 93-104, 2013. Google Scholar
  5. R. Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 16:87-90, 1958. Google Scholar
  6. Michael A. Bender and Martín Farach-Colton. The LCA problem revisited. In LATIN 2000: Theoretical Informatics. Springer Berlin Heidelberg, 2000. Google Scholar
  7. M.W Bern, E.L Lawler, and A.L Wong. Linear-time computation of optimal subgraphs of decomposable graphs. Journal of Algorithms, 8(2):216-235, 1987. Google Scholar
  8. H. L. Bodlaender. Dynamic programming on graphs with bounded treewidth. In ICALP, volume LNCS 317, pages 105-118. Springer, 1988. Google Scholar
  9. H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6), December 1996. Google Scholar
  10. H. L. Bodlaender. Discovering treewidth. In SOFSEM'05, volume LNCS 3381, pages 1-16. Springer, 2005. Google Scholar
  11. Hans L. Bodlaender. A tourist guide through treewidth. Acta Cybern., 11(1-2):1-21, 1993. Google Scholar
  12. HansL. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM Journal on Computing, 27:1725-1746, 1995. Google Scholar
  13. Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. In POPL, pages 733-747, 2016. Google Scholar
  14. Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Prateesh Goyal, and Andreas Pavlogiannis. Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. In POPL, 2015. Google Scholar
  15. Krishnendu Chatterjee, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Faster algorithms for quantitative verification in constant treewidth graphs. In CAV, 2015. Google Scholar
  16. Shiva Chaudhuri and Christos D. Zaroliagis. Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms. Algorithmica, 27:212-226, 1995. Google Scholar
  17. Tobias Columbus. Search space size in contraction hierarchies. Master’s thesis, Karlsruhe Institute of Technology, 2012. Google Scholar
  18. T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction To Algorithms. MIT Press, 2001. Google Scholar
  19. Edsger. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959. Google Scholar
  20. M. Elberfeld, A. Jakoby, and T. Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In FOCS, 2010. Google Scholar
  21. Michael J. Fischer and Albert R. Meyer. Boolean Matrix Multiplication and Transitive Closure. In SWAT (FOCS), pages 129-131. IEEE Computer Society, 1971. Google Scholar
  22. Robert W. Floyd. Algorithm 97: Shortest path. Communications of the ACM, 5(6):345, 1962. Google Scholar
  23. Lester R. Ford. Network Flow Theory. Report P-923, The Rand Corporation, 1956. Google Scholar
  24. Rudolf Halin. S-functions for graphs. Journal of Geometry, 8(1-2):171-186, 1976. Google Scholar
  25. D. Harel and R. Tarjan. Fast Algorithms for Finding Nearest Common Ancestors. SIAM Journal on Computing, 13(2):338-355, 1984. Google Scholar
  26. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. on Systems Science and Cybernetics, 4(2):100-107, 1968. Google Scholar
  27. Donald B. Johnson. Efficient Algorithms for Shortest Paths in Sparse Networks. J. ACM, 24(1):1-13, January 1977. Google Scholar
  28. Edward F. Moore. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching, and Annals of the Computation Laboratory of Harvard University, pages 285-292. Harvard University Press, 1959. Google Scholar
  29. Leon R. Planken, Mathijs M. de Weerdt, and Roman P.J. van der Krogt. Computing all-pairs shortest paths by leveraging low treewidth. In ICAPS-11, pages 170-177. AAAI Press, 2011. Google Scholar
  30. Neil Robertson and P.D Seymour. Graph minors. III. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49-64, 1984. Google Scholar
  31. B. Roy. Transitivité et connexité. C. R. Acad. Sci. Paris, 249:216-218, 1959. Google Scholar
  32. Mikkel Thorup. All Structured Programs Have Small Tree Width and Good Register Allocation. Information and Computation, 142(2):159-181, 1998. Google Scholar
  33. Stephen Warshall. A Theorem on Boolean Matrices. J. ACM, 9(1):11-12, January 1962. Google Scholar
  34. Atsuko Yamaguchi, Kiyoko F. Aoki, and Hiroshi Mamitsuka. Graph complexity of chemical compounds in biological pathways. Genome Informatics, 14:376-377, 2003. Google Scholar
  35. Yosuke Yano, Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In CIKM'13, pages 1601-1606, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact