Document Open Access Logo

Space-Efficient Algorithms for Reachability in Directed Geometric Graphs

Authors Sujoy Bhore , Rahul Jain

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.63.pdf
  • Filesize: 0.99 MB
  • 17 pages

Document Identifiers

Author Details

Sujoy Bhore
  • Indian Institute of Science Education and Research, Bhopal, India
Rahul Jain
  • Fernuniversität in Hagen, Germany

Cite As Get BibTex

Sujoy Bhore and Rahul Jain. Space-Efficient Algorithms for Reachability in Directed Geometric Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.63

Abstract

The problem of graph Reachability is to decide whether there is a path from one vertex to another in a given graph. In this paper, we study the Reachability problem on three distinct graph families - intersection graphs of Jordan regions, unit contact disk graphs (penny graphs), and chordal graphs. For each of these graph families, we present space-efficient algorithms for the Reachability problem. 
For intersection graphs of Jordan regions, we show how to obtain a "good" vertex separator in a space-efficient manner and use it to solve the Reachability in polynomial time and O(m^{1/2} log n) space, where n is the number of Jordan regions, and m is the total number of crossings among the regions. We use a similar approach for chordal graphs and obtain a polynomial time and O(m^{1/2} log n) space algorithm, where n and m are the number of vertices and edges, respectively. However, for unit contact disk graphs (penny graphs), we use a more involved technique and obtain a better algorithm. We show that for every ε > 0, there exists a polynomial time algorithm that can solve Reachability in an n vertex directed penny graph, using O(n^{1/4+ε}) space. We note that the method used to solve penny graphs does not extend naturally to the class of geometric intersection graphs that include arbitrary size cliques.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Reachablity
  • Geometric intersection graphs
  • Space-efficient algorithms

Metrics

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

Related Versions

References

  1. 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
  2. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  3. Tetsuo Asano and Benjamin Doerr. Memory-constrained algorithms for shortest path problem. In CCCG, 2011. Google Scholar
  4. Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, and Osamu Watanabe. Õ(√n)-space and polynomial-time algorithm for planar directed graph reachability. In International Symposium on Mathematical Foundations of Computer Science, pages 45-56. Springer, 2014. Google Scholar
  5. Bahareh Banyassady, Matias Korman, and Wolfgang Mulzer. Geometric algorithms with limited workspace: A survey. CoRR, abs/1806.05868, 2018. URL: http://arxiv.org/abs/1806.05868.
  6. Greg Barnes, Jonathan F Buss, Walter L Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed st connectivity. SIAM Journal on Computing, 27(5):1273-1282, 1998. Google Scholar
  7. Sujoy Bhore and Rahul Jain. Space-efficient algorithms for reachability in geometric graphs. CoRR, abs/2101.05235, 2021. URL: http://arxiv.org/abs/2101.05235.
  8. Paz Carmi, Man-Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada, and Shakhar Smorodinsky. Balanced line separators of unit disk graphs. Comput. Geom., 86, 2020. Google Scholar
  9. Marcia R Cerioli, Luerbio Faria, Talita O Ferreira, and Fábio Protti. A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation. RAIRO-Theoretical Informatics and Applications, 45(3):331-346, 2011. Google Scholar
  10. Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran, and Lin F. Yang. New time-space upperbounds for directed reachability in high-genus and h-minor-free graphs. In Venkatesh Raman and S. P. Suresh, editors, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India, volume 29 of LIPIcs, pages 585-595. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. Google Scholar
  11. Diptarka Chakraborty and Raghunath Tewari. An o(n^ε) space and polynomial time algorithm for reachability in directed layered planar graphs. ACM Trans. Comput. Theory, 9(4):19:1-19:11, 2018. Google Scholar
  12. Steven Chaplick, Vít Jelínek, Jan Kratochvíl, and Tomáš Vyskočil. Bend-bounded path intersection graphs: Sausages, noodles, and waffles on a grill. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 274-285. Springer, 2012. Google Scholar
  13. Brent N Clark, Charles J Colbourn, and David S Johnson. Unit disk graphs. In Annals of Discrete Mathematics, volume 48, pages 165-177. Elsevier, 1991. Google Scholar
  14. Gabriel Andrew Dirac. On rigid circuit graphs. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 25, pages 71-76. Springer, 1961. Google Scholar
  15. Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 383-392, 2014. Google Scholar
  16. Jacob Fox and János Pach. Separator theorems and turán-type results for planar intersection graphs. Advances in Mathematics, 219(3):1070-1080, 2008. Google Scholar
  17. Delbert Fulkerson and Oliver Gross. Incidence matrices and interval graphs. Pacific journal of mathematics, 15(3):835-855, 1965. Google Scholar
  18. Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47-56, 1974. Google Scholar
  19. John R Gilbert, Donald J Rose, and Anders Edenbrandt. A separator theorem for chordal graphs. SIAM Journal on Algebraic Discrete Methods, 5(3):306-313, 1984. Google Scholar
  20. Chetan Gupta, Vimal Raj Sharma, and Raghunath Tewari. Reachability in o (log n) genus graphs is in unambiguous logspace. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  21. Michael Hoffmann, Vincent Kusters, and Tillmann Miltzow. Halving balls in deterministic linear time. In European Symposium on Algorithms, pages 566-578. Springer, 2014. Google Scholar
  22. Hiroshi Imai and Takao Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. Journal of Algorithms, 4(4):310-323, 1983. Google Scholar
  23. Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, and Osamu Watanabe. An o(n^1/2+∑)-space and polynomial-time algorithm for directed planar reachability. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 277-286. IEEE Computer Society, 2013. Google Scholar
  24. Rahul Jain and Raghunath Tewari. An o(n^(1/4 +ε) space and polynomial algorithm for grid graph reachability. In Arkadev Chattopadhyay and Paul Gastin, editors, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019, Bombay, India, volume 150 of LIPIcs, pages 19:1-19:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  25. Rahul Jain and Raghunath Tewari. Reachability in high treewidth graphs. In Pinyan Lu and Guochuan Zhang, editors, 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, volume 149 of LIPIcs, pages 12:1-12:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  26. Harry R Lewis and Christos H Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19(2):161-187, 1982. Google Scholar
  27. Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. Google Scholar
  28. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM (JACM), 55(4):1-24, 2008. Google Scholar
  29. Donald J Rose. Triangulated graphs and the elimination process. Journal of Mathematical Analysis and Applications, 32(3):597-609, 1970. Google Scholar
  30. Donald J Rose. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In Graph theory and computing, pages 183-217. Elsevier, 1972. Google Scholar
  31. Donald J Rose, R Endre Tarjan, and George S Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on computing, 5(2):266-283, 1976. Google Scholar
  32. Walter J Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of computer and system sciences, 4(2):177-192, 1970. Google Scholar
  33. Avi Wigderson. The complexity of graph connectivity. In International Symposium on Mathematical Foundations of Computer Science, pages 112-132. Springer, 1992. 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