Document Open Access Logo

On Counting Oracles for Path Problems

Authors Ivona Bezáková, Andrew Searns

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.56.pdf
  • Filesize: 452 kB
  • 12 pages

Document Identifiers

Author Details

Ivona Bezáková
  • Department of Computer Science, Rochester Institute of Technology, Rochester, NY, USA
Andrew Searns
  • Rochester Institute of Technology, Rochester, NY, USA

Funding

Research supported by NSF grant CCF-1319987 and by an REU (Research Experience for Undergraduates) supplement.

Cite As Get BibTex

Ivona Bezáková and Andrew Searns. On Counting Oracles for Path Problems. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.56

Abstract

We initiate the study of counting oracles for various path problems in graphs. Distance oracles have gained a lot of attention in recent years, with studies of the underlying space and time tradeoffs. For a given graph G, a distance oracle is a data structure which can be used to answer distance queries for pairs of vertices s,t in V(G). In this work, we extend the set up to answering counting queries: for a pair of vertices s,t, the oracle needs to provide the number of (shortest or all) paths from s to t. We present O(n^{1.5}) preprocessing time, O(n^{1.5}) space, and O(sqrt{n}) query time algorithms for oracles counting shortest paths in planar graphs and for counting all paths in planar directed acyclic graphs. We extend our results to other graphs which admit small balanced separators and present applications where our oracle improves the currently best known running times.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Counting oracle
  • Path problems
  • Shortest paths
  • Separators

Metrics

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

References

  1. Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-case Costs. SODA, pages 740-753, 2016. Google Scholar
  2. Mohamad Akra and Louay Bazzi. On the Solution of Linear Recurrence Equations. Computational Optimization and Applications, 10(2):195-210, 1998. Google Scholar
  3. Srinivasa Rao Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel H. M. Smid, and Christos D. Zaroliagis. Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane. In Proceedings of Algorithms - ESA '96, Fourth Annual European Symposium, pages 514-528, 1996. Google Scholar
  4. Michael O. Ball and J. Scott Provan. Calculating Bounds on Reachability and Connectnedness in Stochastic Networks. Networks, 13:253-278, 1983. Google Scholar
  5. Ivona Bezáková and Adam J. Friedlander. Counting and Sampling Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time. Theor. Comp. Sci., 417:2-11, 2012. Google Scholar
  6. Sergio Cabello. Many Distances in Planar Graphs. Algorithmica, 62(1-2):361-381, 2012. Google Scholar
  7. Erin W. Chambers, Kyle Fox, and Amir Nayyeri. Counting and Sampling Minimum Cuts in Genus g Graphs. Discrete & Computational Geometry, 52(3):450-475, 2014. Google Scholar
  8. Danny Z. Chen and Jinhui Xu. Shortest path queries in planar graphs. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 469-478, 2000. Google Scholar
  9. Vincent Cohen-Addad, Søren Dahlgaard, and Christian Wulff-Nilsen. Fast and Compact Exact Distance Oracle for Planar Graphs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 962-973, 2017. Google Scholar
  10. Hristo Djidjev. On-Line Algorithms for Shortest Path Problems on Planar Digraphs. In Proceedings of Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG, pages 151-165, 1996. Google Scholar
  11. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci., 72(5):868-889, 2006. Google Scholar
  12. Jörg Flum and Martin Grohe. The Parameterized Complexity of Counting Problems. SIAM J. Comput., 33(4):892-922, 2004. Google Scholar
  13. Pawel Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen. Better Tradeoffs for Exact Distance Oracles in Planar Graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 515-529, 2018. Google Scholar
  14. John R. Gilber, Joan P. Hutchinson, and Robert Endre Tarjan. A Separator Theorem for Graphs of Bounded Genus. Journal of Algorithms, 5(3):391-405, 1984. Google Scholar
  15. Monika Rauch Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. Faster Shortest-Path Algorithms for Planar Graphs. J. Comput. Syst. Sci., 55(1):3-23, 1997. Google Scholar
  16. Richard J. Lipton and Robert E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. URL: http://dx.doi.org/10.1137/0136016.
  17. Matúš Mihalák, Rastislav Šrámek, and Peter Widmayer. Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs. Theory Comput. Syst., 58(1):45-59, 2016. Google Scholar
  18. Shay Mozes and Christian Sommer. Exact distance oracles for planar graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA,, pages 209-222, 2012. Google Scholar
  19. J. Scott Provan and Michael O. Ball. The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput., 12(4):777-788, 1983. Google Scholar
  20. Leslie G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM J. Comput., 8(3):410-421, 1979. Google Scholar
  21. Masaki Yamamoto. Approximately counting paths and cycles in a graph. Discrete Applied Mathematics, 217:381-387, 2017. 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