Document Open Access Logo

A Framework for In-place Graph Algorithms

Authors Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, Srinivasa Rao Satti

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.13.pdf
  • Filesize: 437 kB
  • 16 pages

Document Identifiers

Author Details

Sankardeep Chakraborty
  • The University of Tokyo, Japan
Anish Mukherjee
  • Chennai Mathematical Institute, India
Venkatesh Raman
  • The Institute of Mathematical Sciences, HBNI, India
Srinivasa Rao Satti
  • Seoul National University, South Korea

Funding

  • Chakraborty, Sankardeep: This work was partially supported by JST CREST Grant Number JPMJCR1402, Japan.

Cite AsGet BibTex

Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti. A Framework for In-place Graph Algorithms. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.13

Abstract

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. A classical result on the ROM model is that any algorithm to sort n numbers using O(s) words of extra space requires Omega (n^2/s) comparisons for lg n <= s <= n/lg n and the bound has also been recently matched by an algorithm. However, if we relax the model, we do have sorting algorithms (say Heapsort) that can sort using O(n lg n) comparisons using O(lg n) bits of extra space, even keeping a permutation of the given input sequence at anytime during the algorithm. We address similar relaxations for graph algorithms. We show that a simple natural relaxation of ROM model allows us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM. By simply allowing elements in the adjacency list of a vertex to be permuted, we show that, on an undirected or directed connected graph G having n vertices and m edges, the vertices of G can be output in a DFS or BFS order using O(lg n) bits of extra space and O(n^3 lg n) time. Thus we obtain similar bounds for reachability and shortest path distance (both for undirected and directed graphs). With a little more (but still polynomial) time, we can also output vertices in the lex-DFS order. As reachability in directed graphs (even in DAGs) and shortest path distance (even in undirected graphs) are NL-complete, and lex-DFS is P-complete, our results show that our model is more powerful than ROM if L != P. En route, we also introduce and develop algorithms for another relaxation of ROM where the adjacency lists of the vertices are circular lists and we can modify only the heads of the lists. Here we first show a linear time DFS implementation using n + O(lg n) bits of extra space. Improving the extra space exponentially to only O(lg n) bits, we also obtain BFS and DFS albeit with a slightly slower running time. Both the models we propose maintain the graph structure throughout the algorithm, only the order of vertices in the adjacency list changes. In sharp contrast, for BFS and DFS, to the best of our knowledge, there are no algorithms in ROM that use even O(n^{1-epsilon}) bits of extra space; in fact, implementing DFS using cn bits for c<1 has been mentioned as an open problem. Furthermore, DFS (BFS, respectively) algorithms using n+o(n) (o(n), respectively) bits of extra use Reingold's [JACM, 2008] or Barnes et al's reachability algorithm [SICOMP, 1998] and hence have high runtime. Our results can be contrasted with the recent result of Buhrman et al. [STOC, 2014] which gives an algorithm for directed st-reachability on catalytic Turing machines using O(lg n) bits with catalytic space O(n^2 lg n) and time O(n^9).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Models of computation
Keywords
  • DFS
  • BFS
  • in-place algorithm
  • space-efficient graph algorithms
  • logspace

Metrics

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

Related Versions

References

  1. A. Aggarwal and R. J. Anderson. A random NC algorithm for depth first search. Combinatorica, 8(1):1-12, 1988. URL: http://dx.doi.org/10.1007/BF02122548.
  2. A. Aggarwal, R. J. Anderson, and M. Kao. Parallel depth-first search in general directed graphs. SIAM J. Comput., 19(2):397-409, 1990. URL: http://dx.doi.org/10.1137/0219025.
  3. N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999. URL: http://dx.doi.org/10.1006/jcss.1997.1545.
  4. R. J. Anderson and E. W. Mayr. Parallelism and the maximal path problem. Inf. Process. Lett., 24(2):121-126, 1987. URL: http://dx.doi.org/10.1016/0020-0190(87)90105-0.
  5. S. Arora and B. Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  6. T. Asano, K. Buchin, M. Buchin, M.Korman, W. Mulzer, G. Rote, and A. Schulz. Reprint of: Memory-constrained algorithms for simple polygons. Comput. Geom., 47(3):469-479, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2013.11.004.
  7. T. Asano, T. Izumi, M. Kiyomi, M. Konagaya, H. Ono, Y. Otachi, P. Schweitzer, J. Tarui, and R. Uehara. Depth-first search using O(n) bits. In 25th ISAAC, pages 553-564, 2014. Google Scholar
  8. T. Asano, D. G. Kirkpatrick, K. Nakagawa, and O. Watanabe. Õ(n)-space and polynomial-time algorithm for planar directed graph reachability. In 39th MFCS LNCS 8634, pages 45-56, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_5.
  9. T. Asano, W. Mulzer, G. Rote, and Y. Wang. Constant-work-space algorithms for geometric problems. JoCG, 2(1):46-68, 2011. URL: http://jocg.org/index.php/jocg/article/view/30.
  10. N. Banerjee, S. Chakraborty, and V. Raman. Improved space efficient algorithms for BFS,DFS and applications. In 22nd COCOON, 2016. URL: http://arxiv.org/abs/1606.04718.
  11. N. Banerjee, S. Chakraborty, V. Raman, S. Roy, and S. Saurabh. Time-space tradeoffs for dynamic programming in trees and bounded treewidth graphs. In 21st COCOON, volume 9198, pages 349-360. springer, LNCS, 2015. Google Scholar
  12. L. Barba, M. Korman, S. Langerman, K. Sadakane, and R. I. Silveira. Space-time trade-offs for stack-based algorithms. Algorithmica, 72(4):1097-1129, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9893-5.
  13. G. Barnes, J. Buss, W. Ruzzo, and B. Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM J. Comput., 27(5):1273-1282, 1998. URL: http://dx.doi.org/10.1137/S0097539793283151.
  14. Paul Beame. A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput., 20(2):270-277, 1991. URL: http://dx.doi.org/10.1137/0220017.
  15. A. Borodin and S. A. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput., 11(2):287-297, 1982. URL: http://dx.doi.org/10.1137/0211022.
  16. A. Borodin, M. J. Fischer, D. G. Kirkpatrick, N. A. Lynch, and M. Tompa. A time-space tradeoff for sorting on non-oblivious machines. J. Comput. Syst. Sci., 22(3):351-364, 1981. URL: http://dx.doi.org/10.1016/0022-0000(81)90037-4.
  17. H. Brönnimann, T. M. Chan, and E. Y. Chen. Towards in-place geometric algorithms and data structures. In Proceedings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, June 8-11, 2004, pages 239-246, 2004. URL: http://dx.doi.org/10.1145/997817.997854.
  18. H. Buhrman, R. Cleve, M. Koucký, B. Loff, and F. Speelman. Computing with a full memory: catalytic space. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 857-866, 2014. URL: http://dx.doi.org/10.1145/2591796.2591874.
  19. H. Buhrman, M.l Koucký, B. Loff, and F. Speelman. Catalytic space: Non-determinism and hierarchy. In 33rd STACS 2016, February 17-20, 2016, Orléans, France, pages 24:1-24:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.24.
  20. D. Chakraborty, A. Pavan, R. Tewari, N. V. Vinodchandran, and L. Yang. New time-space upperbounds for directed reachability in high-genus and h-minor-free graphs. In FSTTCS, pages 585-595, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2014.585.
  21. S. Chakraborty, A. Mukherjee, V. Raman, and S. R. Satti. Frameworks for designing in-place graph algorithms. CoRR, abs/1711.09859, 2017. URL: http://arxiv.org/abs/1711.09859.
  22. S. Chakraborty, V. Raman, and S. R. Satti. Biconnectivity, chain decomposition and st-numbering using O(n) bits. In 27th ISAAC, pages 22:1-22:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2016.22.
  23. S. Chakraborty, V. Raman, and S. R. Satti. Biconnectivity, st-numbering and other applications of DFS using O(n) bits. J. Comput. Syst. Sci., 90:63-79, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2017.06.006.
  24. S. Chakraborty and S. R. Satti. Space-efficient algorithms for maximum cardinality search, stack bfs, queue BFS and applications. In Computing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings, pages 87-98, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62389-4_8.
  25. T. M. Chan and E. Y. Chen. Multi-pass geometric algorithms. Discrete & Computational Geometry, 37(1):79-102, 2007. URL: http://dx.doi.org/10.1007/s00454-006-1275-6.
  26. T. M. Chan, J. I. Munro, and V. Raman. Faster, space-efficient selection algorithms in read-only memory for integers. In Algorithms and Computation - 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings, pages 405-412, 2013. URL: http://dx.doi.org/10.1007/978-3-642-45030-3_38.
  27. T. M. Chan, J. I. Munro, and V. Raman. Selection and sorting in the "restore" model. In 25th-SODA, pages 995-1004, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.74.
  28. S. A. Cook and C. Rackoff. Space lower bounds for maze threadability on restricted machines. SIAM J. Comput., 9(3):636-652, 1980. URL: http://dx.doi.org/10.1137/0209048.
  29. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  30. O. Darwish and A. Elmasry. Optimal time-space tradeoff for the 2d convex-hull problem. In 22th ESA, pages 284-295, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_24.
  31. S. Datta, N. Limaye, P. Nimbhorkar, T. Thierauf, and F. Wagner. Planar graph isomorphism is in log-space. In 24th CCC, pages 203-214, 2009. URL: http://dx.doi.org/10.1109/CCC.2009.16.
  32. Y. Dodis, M. Patrascu, and M. Thorup. Changing base without losing space. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 593-602, 2010. URL: http://dx.doi.org/10.1145/1806689.1806770.
  33. J. Edmonds, C. K. Poon, and D. Achlioptas. Tight lower bounds for st-connectivity on the NNJAG model. SIAM J. Comput., 28(6):2257-2284, 1999. URL: http://dx.doi.org/10.1137/S0097539795295948.
  34. M. Elberfeld, A. Jakoby, and T. Tantau. Logspace versions of the theorems of bodlaender and courcelle. In 51th FOCS, pages 143-152, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.21.
  35. M. Elberfeld and K. Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 383-392, 2014. URL: http://dx.doi.org/10.1145/2591796.2591865.
  36. M. Elberfeld and P. Schweitzer. Canonizing graphs of bounded tree width in logspace. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 32:1-32:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.32.
  37. A. Elmasry, T. Hagerup, and F. Kammer. Space-efficient basic graph algorithms. In 32nd STACS, pages 288-301, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.288.
  38. A. Elmasry, D. D. Juhl, J. Katajainen, and S. R. Satti. Selection from read-only memory with limited workspace. Theor. Comput. Sci., 554:64-73, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2014.06.012.
  39. J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. On graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2-3):207-216, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.013.
  40. G. Franceschini and J. Ian Munro. Implicit dictionaries with O(1) modifications per update and fast search. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 404-413, 2006. Google Scholar
  41. G. Franceschini and S. Muthukrishnan. In-place suffix sorting. In Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, pages 533-545, 2007. URL: http://dx.doi.org/10.1007/978-3-540-73420-8_47.
  42. G. Franceschini, S. Muthukrishnan, and M. Patrascu. Radix sorting with no extra space. In Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, pages 194-205, 2007. URL: http://dx.doi.org/10.1007/978-3-540-75520-3_19.
  43. G. N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci., 34(1):19-26, 1987. URL: http://dx.doi.org/10.1016/0022-0000(87)90002-X.
  44. T. Hagerup and F. Kammer. Succinct choice dictionaries. CoRR, abs/1604.06058, 2016. URL: http://arxiv.org/abs/1604.06058,
  45. F. Kammer, D. Kratsch, and M. Laudahn. Space-efficient biconnected components and recognition of outerplanar graphs. In 41st MFCS, 2016. Google Scholar
  46. M. Koucký. Catalytic computation. Bulletin of the EATCS, 118, 2016. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/400.
  47. T. W. Lai and D. Wood. Implicit selection. In SWAT 88, 1st Scandinavian Workshop on Algorithm Theory, Halmstad, Sweden, July 5-8, 1988, Proceedings, pages 14-23, 1988. URL: http://dx.doi.org/10.1007/3-540-19487-8_2.
  48. A. McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43(1):9-20, 2014. URL: http://dx.doi.org/10.1145/2627692.2627694.
  49. J. I. Munro and M. Paterson. Selection and sorting with limited storage. Theor. Comput. Sci., 12:315-323, 1980. URL: http://dx.doi.org/10.1016/0304-3975(80)90061-4.
  50. J. I. Munro and V. Raman. Selection from read-only memory and sorting with minimum data movement. Theor. Comput. Sci., 165(2):311-323, 1996. URL: http://dx.doi.org/10.1016/0304-3975(95)00225-1.
  51. J. Ian Munro. An implicit data structure supporting insertion, deletion, and search in O(log² n) time. J. Comput. Syst. Sci., 33(1):66-74, 1986. URL: http://dx.doi.org/10.1016/0022-0000(86)90043-7.
  52. J. Pagter and T. Rauhe. Optimal time-space trade-offs for sorting. In 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA, pages 264-268, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743455.
  53. J. H. Reif. Symmetric complementation. J. ACM, 31(2):401-421, 1984. URL: http://dx.doi.org/10.1145/62.322436.
  54. J. H. Reif. Depth-first search is inherently sequential. Inf. Process. Lett., 20(5):229-234, 1985. URL: http://dx.doi.org/10.1016/0020-0190(85)90024-9.
  55. O. Reingold. Undirected connectivity in log-space. J. ACM, 55(4), 2008. URL: http://dx.doi.org/10.1145/1391289.1391291.
  56. T. Tantau. Logspace optimization problems and their approximability properties. Theory Comput. Syst., 41(2):327-350, 2007. URL: http://dx.doi.org/10.1007/s00224-007-2011-1.
  57. M. Tompa. Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations. SIAM J. Comput., 11(1):130-137, 1982. URL: http://dx.doi.org/10.1137/0211010.
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 Imprint Privacy Contact