Document Open Access Logo

Tree Exploration in Dual-Memory Model

Authors Dominik Bojko , Karol Gotfryd , Dariusz R. Kowalski, Dominik Pająk

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.22.pdf
  • Filesize: 0.85 MB
  • 16 pages

Document Identifiers

Author Details

Dominik Bojko
  • Department of Fundamentals of Computer Science, Wroclaw University of Science and Technology, Poland
Karol Gotfryd
  • Department of Fundamentals of Computer Science, Wroclaw University of Science and Technology, Poland
Dariusz R. Kowalski
  • School of Computer and Cyber Sciences, Augusta University, GA, USA
Dominik Pająk
  • Department of Pure Mathematics, Wroclaw University of Science and Technology, Infermedica, Poland

Funding

  • Pająk, Dominik: Supported by Polish National Science Centre grant UMO-2019/33/B/ST6/ 02988.

Cite AsGet BibTex

Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, and Dominik Pająk. Tree Exploration in Dual-Memory Model. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.22

Abstract

We study the problem of online tree exploration by a deterministic mobile agent. Our main objective is to establish what features of the model of the mobile agent and the environment allow linear exploration time. We study agents that, upon entering a node, do not receive as input the edge via which they entered. In such model, deterministic memoryless exploration is infeasible, hence the agent needs to be allowed to use some memory. The memory can be located at the agent or at each node. The existing lower bounds show that if the memory is either only at the agent or only at the nodes, then the exploration needs superlinear time. We show that tree exploration in dual-memory model, with constant memory at the agent and logarithmic in the degree at each node is possible in linear time when one of the two additional features is present: fixed initial state of the memory at each node (so called clean memory) or a single movable token. We present two algorithms working in linear time for arbitrary trees in these two models. On the other hand, in our lower bound we show that if the agent has a single bit of memory and one bit is present at each node, then the exploration may require quadratic time even on paths, if the initial memory at nodes could be set arbitrarily (so called dirty memory). This shows that having clean node memory or a token allows linear time exploration of trees in the dual-memory model, but having neither of those features may lead to quadratic exploration time even on a simple path.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Online algorithms
Keywords
  • Graph exploration
  • agent
  • memory
  • tree
  • deterministic algorithms
  • lower bound

Metrics

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

Related Versions

References

  1. Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pages 218-223. IEEE Computer Society, 1979. URL: https://doi.org/10.1109/SFCS.1979.34.
  2. Evangelos Bampas, Leszek Gąsieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing, Adrian Kosowski, and Tomasz Radzik. Robustness of the Rotor-Router Mechanism. Algorithmica, 78(3):869-895, 2017. URL: https://doi.org/10.1007/s00453-016-0179-y.
  3. Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, and Salil P. Vadhan. The Power of a Pebble: Exploring and Mapping Directed Graphs. Inf. Comput., 176(1):1-21, 2002. URL: https://doi.org/10.1006/inco.2001.3081.
  4. Michael A. Bender and Donna K. Slonim. The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 75-85, 1994. URL: https://doi.org/10.1109/SFCS.1994.365703.
  5. Petra Berenbrink, Colin Cooper, and Tom Friedetzky. Random Walks Which Prefer Unvisited Edges: Exploring High Girth Even Degree Expanders in Linear Time. Random Struct. Algorithms, 46(1):36-54, 2015. URL: https://doi.org/10.1002/rsa.20504.
  6. Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, and Dominik Pajak. Tree exploration in dual-memory model, 2022. (Full version). URL: http://arxiv.org/abs/2112.13449.
  7. Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1):107-117, 1998. Proceedings of the Seventh International World Wide Web Conference. URL: https://doi.org/10.1016/S0169-7552(98)00110-X.
  8. Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, and David Peleg. Label-Guided Graph Exploration by a Finite Automaton. ACM Trans. Algorithms, 4(4):42:1-42:18, August 2008. URL: https://doi.org/10.1145/1383369.1383373.
  9. H. K. Dai and Kevin E. Flannery. Improved Length Lower Bounds for Reflecting Sequences. In Jin-Yi Cai and Chak Kuen Wong, editors, Computing and Combinatorics, pages 56-67. Springer Berlin Heidelberg, 1996. URL: https://doi.org/10.1007/3-540-61332-3_139.
  10. Shantanu Das. Graph Explorations with Mobile Agents. In Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors, Distributed Computing by Mobile Entities: Current Research in Moving and Computing, Lecture Notes in Computer Science, pages 403-422. Springer International Publishing, Cham, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7_16.
  11. Shantanu Das and Nicola Santoro. Moving and Computing Models: Agents. In Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors, Distributed Computing by Mobile Entities: Current Research in Moving and Computing, Lecture Notes in Computer Science, pages 15-34. Springer International Publishing, Cham, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7_2.
  12. Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pająk, and Przemysław Uznański. Fast collaborative graph exploration. Inf. Comput., 243:37-49, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.005.
  13. Dariusz Dereniowski, Adrian Kosowski, Dominik Pająk, and Przemyslaw Uznanski. Bounds on the cover time of parallel rotor walks. J. Comput. Syst. Sci., 82(5):802-816, 2016. URL: https://doi.org/10.1016/j.jcss.2016.01.004.
  14. Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, and Andrzej Pelc. Tree exploration with little memory. J. Algorithms, 51(1):38-63, 2004. URL: https://doi.org/10.1016/j.jalgor.2003.10.002.
  15. Yann Disser, Jan Hackfeld, and Max Klimm. Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents. J. ACM, 66(6), October 2019. URL: https://doi.org/10.1145/3356883.
  16. Yann Disser, Frank Mousset, Andreas Noever, Nemanja Škorić, and Angelika Steger. A general lower bound for collaborative tree exploration. Theoretical Computer Science, 811:70-78, 2020. URL: https://doi.org/10.1016/j.tcs.2018.03.006.
  17. Mirosław Dynia, Jakub Łopuszański, and Christian Schindelhauer. Why Robots Need Maps. In G. Prencipe and S. Zaks, editors, Structural Information and Communication Complexity, volume 4474 of Lecture Notes in Computer Science, pages 41-50. Springer Berlin Heidelberg, 2007. URL: https://doi.org/10.1007/978-3-540-72951-8_5.
  18. Klim Efremenko and Omer Reingold. How Well Do Random Walks Parallelize? In Irit Dinur, Klaus Jansen, Joseph Naor, and José Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 5687 of Lecture Notes in Computer Science, pages 476-489. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_36.
  19. Robert Elsässer and Thomas Sauerwald. Tight bounds for the cover time of multiple random walks. Theor. Comput. Sci., 412(24):2623-2641, 2011. URL: https://doi.org/10.1016/j.tcs.2010.08.010.
  20. Uriel Feige. A Tight Lower Bound on the Cover Time for Random Walks on Graphs. Random Struct. Algorithms, 6(4):433-438, 1995. URL: https://doi.org/10.1002/rsa.3240060406.
  21. Uriel Feige. A Tight Upper Bound on the Cover Time for Random Walks on Graphs. Random Struct. Algorithms, 6(1):51-54, 1995. URL: https://doi.org/10.1002/rsa.3240060106.
  22. Pierre Fraigniaud, Leszek Gąsieniec, Dariusz R. Kowalski, and Andrzej Pelc. Collective Tree Exploration. Networks, 48(3):166-177, 2006. URL: https://doi.org/10.1002/net.20127.
  23. Pierre Fraigniaud and David Ilcinkas. Digraphs Exploration with Little Memory. In V. Diekert and M. Habib, editors, STACS 2004, volume 2996 of Lecture Notes in Computer Science, pages 246-257. Springer Berlin Heidelberg, 2004. URL: https://doi.org/10.1007/978-3-540-24749-4_22.
  24. Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, and David Peleg. Graph exploration by a finite automaton. Theor. Comput. Sci., 345(2-3):331-344, 2005. URL: https://doi.org/10.1016/j.tcs.2005.07.014.
  25. Pierre Fraigniaud, David Ilcinkas, Sergio Rajsbaum, and Sébastien Tixeuil. Space Lower Bounds for Graph Exploration via Reduced Automata. In A. Pelc and M. Raynal, editors, Structural Information and Communication Complexity, volume 3499 of Lecture Notes in Computer Science, pages 140-154. Springer Berlin Heidelberg, 2005. URL: https://doi.org/10.1007/11429647_13.
  26. Leszek Gąsieniec and Tomasz Radzik. Memory Efficient Anonymous Graph Exploration. In H. Broersma, T. Erlebach, T. Friedetzky, and D. Paulusma, editors, Graph-Theoretic Concepts in Computer Science, volume 5344 of Lecture Notes in Computer Science, pages 14-29. Springer Berlin Heidelberg, 2008. URL: https://doi.org/10.1007/978-3-540-92248-3_2.
  27. Ralf Klasing, Adrian Kosowski, Dominik Pająk, and Thomas Sauerwald. The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks. Distributed Comput., 30(2):127-148, 2017. URL: https://doi.org/10.1007/s00446-016-0282-y.
  28. Adrian Kosowski. Faster Walks in Graphs: A Õ(n²) Time-Space Trade-off for Undirected s-t Connectivity. In Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1873-1883. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.133.
  29. Adrian Kosowski and Dominik Pająk. Does adding more agents make a difference? A case study of cover time for the rotor-router. J. Comput. Syst. Sci., 106:80-93, 2019. URL: https://doi.org/10.1016/j.jcss.2019.07.001.
  30. Michal Koucký. Universal traversal sequences with backtracking. Journal of Computer and System Sciences, 65(4):717-726, 2002. URL: https://doi.org/10.1016/S0022-0000(02)00023-5.
  31. Michal Koucký. Log-space constructible universal traversal sequences for cycles of length O(n^4.03). Theor. Comput. Sci., 296(1):117-144, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00436-X.
  32. László Lovász. Random Walks on Graphs: A Survey. Combinatorics, Paul Erdos is Eighty. Bolyai Soc. Math. Stud., 2:1-46, 1993. Google Scholar
  33. Nicole Megow, Kurt Mehlhorn, and Pascal Schweitzer. Online graph exploration: New results on old and new algorithms. Theoretical Computer Science, 463:62-72, 2012. Special Issue on Theory and Applications of Graph Searching Problems. URL: https://doi.org/10.1016/j.tcs.2012.06.034.
  34. Artur Menc, Dominik Pająk, and Przemysław Uznański. Time and space optimality of rotor-router graph exploration. Inf. Process. Lett., 127:17-20, 2017. URL: https://doi.org/10.1016/j.ipl.2017.06.010.
  35. Nathan Michael et al. Collaborative Mapping of an Earthquake-Damaged Building via Ground and Aerial Robots. Journal of Field Robotics, 29(5):832-841, 2012. URL: https://doi.org/10.1002/rob.21436.
  36. Yoshiaki Nonaka, Hirotaka Ono, Kunihiko Sadakane, and Masafumi Yamashita. The hitting and cover times of Metropolis walks. Theor. Comput. Sci., 411(16-18):1889-1894, 2010. URL: https://doi.org/10.1016/j.tcs.2010.01.032.
  37. Christian Ortolf and Christian Schindelhauer. A Recursive Approach to Multi-robot Exploration of Trees. In Magnús M. Halldórsson, editor, Structural Information and Communication Complexity, volume 8576 of Lecture Notes in Computer Science, pages 343-354. Springer International Publishing, 2014. URL: https://doi.org/10.1007/978-3-319-09620-9_26.
  38. Omer Reingold. Undirected Connectivity in Log-Space. J. ACM, 55(4), September 2008. URL: https://doi.org/10.1145/1391289.1391291.
  39. H. A. Rollik. Automaten in planaren Graphen. Acta Inf., 13(3):287-298, March 1980. URL: https://doi.org/10.1007/BF00288647.
  40. Yuichi Sudo, Fukuhito Ooshita, and Sayaka Kamei. Self-stabilizing Graph Exploration by a Single Agent. CoRR, abs/2010.08929, 2020. URL: http://arxiv.org/abs/2010.08929.
  41. Vladimir Yanovski, Israel A. Wagner, and Alfred M. Bruckstein. A Distributed Ant Algorithm for Efficiently Patrolling a Network. Algorithmica, 37(3):165-186, 2003. URL: https://doi.org/10.1007/s00453-003-1030-9.
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