Document Open Access Logo

Deterministic Graph Exploration with Advice

Authors Barun Gorain, Andrzej Pelc

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.132.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Barun Gorain
Andrzej Pelc

Cite As Get BibTex

Barun Gorain and Andrzej Pelc. Deterministic Graph Exploration with Advice. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 132:1-132:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.132

Abstract

We consider the task of graph exploration. An n-node graph has unlabeled nodes, and all ports at any node of degree d are arbitrarily numbered 0,..., d-1. A mobile agent has to visit all nodes and stop. The exploration time is the number of edge traversals. We consider the problem of how much knowledge the agent has to have a priori, in order to explore the graph in a given time, using a deterministic algorithm.  This a priori information (advice) is provided to the agent by an oracle, in the form of a binary string, whose length is called the size of advice. We consider two types of oracles. The instance oracle knows the entire instance of the exploration problem, i.e., the port-numbered map of the graph and the starting node of the agent in this map. The map oracle knows the port-numbered map of the graph but does not know the starting node of the agent. What is the minimum size of advice that must be given to the agent by each of these oracles, so that the agent explores the graph in a given time?


We first consider exploration in polynomial time, and determine the exact minimum size of advice to achieve it. This size is log(log(log(n))) - Theta(1), for both types of oracles.

When advice is large, there are two natural time thresholds: Theta(n^2) for a map oracle, and Theta(n) for an instance oracle, that can be achieved with sufficiently large advice. We show that, with a map oracle, time Theta(n^2) cannot be improved in general, regardless of the size of advice. We also show that the smallest size of advice to achieve this time is larger than n^delta, for any delta <1/3.

For an instance oracle, advice of size O(n*log(n)) is enough to  achieve time O(n). We show that, with any advice of size 
o(n*log(n)), the time of exploration must be at least n^epsilon, for any epsilon <2, and with any advice of size O(n), the time must be Omega(n^2).

We also investigate minimum advice sufficient for fast exploration of Hamiltonian graphs.

Subject Classification

Keywords
  • algorithm
  • graph
  • exploration
  • mobile agent
  • advice

Metrics

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

References

  1. Serge Abiteboul, Stephen Alstrup, Haim Kaplan, Tova Milo, and Theis Rauhe. Compact labeling scheme for ancestor queries. SIAM J. Comput., 35(6):1295-1309, 2006. URL: http://dx.doi.org/10.1137/S0097539703437211.
  2. Susanne Albers and Monika Rauch Henzinger. Exploring unknown environments. SIAM J. Comput., 29(4):1164-1188, 2000. URL: http://dx.doi.org/10.1137/S009753979732428X.
  3. 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: http://dx.doi.org/10.1109/SFCS.1979.34.
  4. Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, and Mona Singh. Piecemeal graph exploration by a mobile robot. Inf. Comput., 152(2):155-172, 1999. URL: http://dx.doi.org/10.1006/inco.1999.2795.
  5. Eldad Bar-Eli, Piotr Berman, Amos Fiat, and Peiyuan Yan. Online navigation in a room. J. Algorithms, 17(3):319-341, 1994. URL: http://dx.doi.org/10.1006/jagm.1994.1039.
  6. 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: http://dx.doi.org/10.1006/inco.2001.3081.
  7. Michael A. Bender and Donna K. Slonim. The power of team exploration: Two robots can learn unlabeled directed graphs. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 75-85. IEEE Computer Society, 1994. URL: http://dx.doi.org/10.1109/SFCS.1994.365703.
  8. Margrit Betke, Ronald L. Rivest, and Mona Singh. Piecemeal learning of an unknown environment. Machine Learning, 18(2-3):231-254, 1995. URL: http://dx.doi.org/10.1007/BF00993411.
  9. Avrim Blum, Prabhakar Raghavan, and Baruch Schieber. Navigating in unfamiliar geometric terrain. SIAM J. Comput., 26(1):110-137, 1997. URL: http://dx.doi.org/10.1137/S0097539791194931.
  10. Allan Borodin, Walter L. Ruzzo, and Martin Tompa. Lower bounds on the length of universal traversal sequences. J. Comput. Syst. Sci., 45(2):180-203, 1992. URL: http://dx.doi.org/10.1016/0022-0000(92)90046-L.
  11. Jérémie Chalopin, Shantanu Das, and Adrian Kosowski. Constructing a map of an anonymous graph: Applications of universal sequences. In Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah, editors, Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14-17, 2010. Proceedings, volume 6490 of Lecture Notes in Computer Science, pages 119-134. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-17653-1_10.
  12. Xiaotie Deng, Tiko Kameda, and Christos H. Papadimitriou. How to learn an unknown environment I: the rectilinear case. J. ACM, 45(2):215-245, 1998. URL: http://dx.doi.org/10.1145/274787.274788.
  13. Dariusz Dereniowski and Andrzej Pelc. Drawing maps with advice. J. Parallel Distrib. Comput., 72(2):132-143, 2012. URL: http://dx.doi.org/10.1016/j.jpdc.2011.10.004.
  14. Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, and Andrzej Pelc. Tree exploration with little memory. J. Algorithms, 51(1):38-63, 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2003.10.002.
  15. Stefan Dobrev, Rastislav Královic, and Euripides Markou. Online graph exploration with advice. In Guy Even and Magnús M. Halldórsson, editors, Structural Information and Communication Complexity - 19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30-July 2, 2012, Revised Selected Papers, volume 7355 of Lecture Notes in Computer Science, pages 267-278. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31104-8_23.
  16. Christian A. Duncan, Stephen G. Kobourov, and V. S. Anil Kumar. Optimal constrained graph exploration. ACM Trans. Algorithms, 2(3):380-402, 2006. URL: http://dx.doi.org/10.1145/1159892.1159897.
  17. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice. Theor. Comput. Sci., 412(24):2642-2656, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.08.007.
  18. Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. Distributed computing with advice: information sensitivity of graph coloring. Distributed Computing, 21(6):395-403, 2009. URL: http://dx.doi.org/10.1007/s00446-008-0076-y.
  19. Pierre Fraigniaud and David Ilcinkas. Digraphs exploration with little memory. In Volker Diekert and Michel Habib, editors, STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings, volume 2996 of Lecture Notes in Computer Science, pages 246-257. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-24749-4_22.
  20. Pierre Fraigniaud, David Ilcinkas, and Andrzej Pelc. Tree exploration with advice. Inf. Comput., 206(11):1276-1287, 2008. URL: http://dx.doi.org/10.1016/j.ic.2008.07.005.
  21. Pierre Fraigniaud, David Ilcinkas, and Andrzej Pelc. Communication algorithms with advice. J. Comput. Syst. Sci., 76(3-4):222-232, 2010. URL: http://dx.doi.org/10.1016/j.jcss.2009.07.002.
  22. Pierre Fraigniaud, Amos Korman, and Emmanuelle Lebhar. Local MST computation with short advice. Theory Comput. Syst., 47(4):920-933, 2010. URL: http://dx.doi.org/10.1007/s00224-010-9280-9.
  23. Emanuele G. Fusco and Andrzej Pelc. Trade-offs between the size of advice and broadcasting time in trees. Algorithmica, 60(4):719-734, 2011. URL: http://dx.doi.org/10.1007/s00453-009-9361-9.
  24. Emanuele G. Fusco, Andrzej Pelc, and Rossella Petreschi. Topology recognition with advice. Inf. Comput., 247:254-265, 2016. URL: http://dx.doi.org/10.1016/j.ic.2016.01.005.
  25. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. J. Algorithms, 53(1):85-112, 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2004.05.002.
  26. David Ilcinkas, Dariusz R. Kowalski, and Andrzej Pelc. Fast radio broadcasting with advice. Theor. Comput. Sci., 411(14-15):1544-1557, 2010. URL: http://dx.doi.org/10.1016/j.tcs.2010.01.004.
  27. Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215-233, 2010. URL: http://dx.doi.org/10.1007/s00446-010-0095-3.
  28. Robert Krauthgamer, editor. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.
  29. Nicolas Nisse and David Soguet. Graph searching with advice. Theor. Comput. Sci., 410(14):1307-1318, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.08.020.
  30. Petrisor Panaite and Andrzej Pelc. Exploring unknown undirected graphs. J. Algorithms, 33(2):281-295, 1999. URL: http://dx.doi.org/10.1006/jagm.1999.1043.
  31. Petrisor Panaite and Andrzej Pelc. Optimal broadcasting in faulty trees. J. Parallel Distrib. Comput., 60(5):566-584, 2000. URL: http://dx.doi.org/10.1006/jpdc.2000.1625.
  32. Andrzej Pelc and Anas Tiane. Efficient grid exploration with a stationary token. Int. J. Found. Comput. Sci., 25(3):247-262, 2014. URL: http://dx.doi.org/10.1142/S0129054114500129.
  33. Nageswara S. V. Rao, Srikumar Kareti, Weimin Shi, and S. Sitharama Iyengar. Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms, Jul 1993. URL: http://dx.doi.org/10.2172/10180101.
  34. Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1-17:24, 2008. URL: http://dx.doi.org/10.1145/1391289.1391291.
  35. A. Pelc Y. Dieudonné. Impact of knowledge on election time in anonymous networks. In Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2017), 2017. URL: http://dx.doi.org/10.1007/978-3-642-17653-1_10.
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