Document Open Access Logo

Binary Search in Graphs Revisited

Authors Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.20.pdf
  • Filesize: 468 kB
  • 14 pages

Document Identifiers

Author Details

Argyrios Deligkas
George B. Mertzios
Paul G. Spirakis

Cite As Get BibTex

Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis. Binary Search in Graphs Revisited. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.20

Abstract

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by [Emamjomeh-Zadeh et al., STOC, 2016] to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates’ set for the target, while each query asks an appropriately chosen vertex– the "median"–which minimises a potential \Phi among the vertices of the candidates' set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates' set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential Γ that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential \Gamma that allows querying approximate medians.

Subject Classification

Keywords
  • binary search
  • graph
  • approximate query
  • probabilistic algorithm
  • lower bound.

Metrics

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

References

  1. Yosi Ben-Asher, Eitan Farchi, and Ilan Newman. Optimal search in trees. SIAM J. Comput., 28(6):2090-2102, 1999. Google Scholar
  2. Michael Ben-Or and Avinatan Hassidim. The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well). In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 221-230, 2008. Google Scholar
  3. Lucas Boczkowski, Amos Korman, and Yoav Rodeh. Searching on trees with noisy memory. CoRR, abs/1611.01403, 2016. Google Scholar
  4. Renato Carmo, Jair Donadelli, Yoshiharu Kohayakawa, and Eduardo Sany Laber. Searching in random partially ordered sets. Theor. Comput. Sci., 321(1):41-57, 2004. Google Scholar
  5. Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Marco Molinaro. On the complexity of searching in trees and partially ordered structures. Theor. Comput. Sci., 412(50):6879-6896, 2011. Google Scholar
  6. Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Caio Dias Valentim. The binary identification problem for weighted trees. Theor. Comput. Sci., 459:100-112, 2012. Google Scholar
  7. Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, and Elad Verbin. Sorting and selection in posets. SIAM J. Comput., 40(3):597-622, 2011. Google Scholar
  8. Dariusz Dereniowski. Edge ranking and searching in partial orders. Discrete Applied Mathematics, 156(13):2493-2500, 2008. Google Scholar
  9. Dingzhu Du and Frank K. Hwang. Combinatorial Group Testing and its Applications. World Scientific, Singapore, 1993. Google Scholar
  10. Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal. Deterministic and probabilistic binary search in graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 519-532, 2016. Google Scholar
  11. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM J. Comput., 23(5):1001-1018, 1994. Google Scholar
  12. Ehud Fonio, Yael Heyman, Lucas Boczkowski, Aviram Gelblum, Adrian Kosowski, Amos Korman, and Ofer Feinerman. A locally-blazed ant trail achieves efficient collective navigation despite limited information. eLife, page 23 pages, 2016. Google Scholar
  13. Ananth V. Iyer, H. Donald Ratliff, and Gopalakrishnan Vijayan. Optimal node ranking of trees. Inf. Process. Lett., 28(5):225-229, 1988. Google Scholar
  14. C. Jordan. Sur les assemblages de lignes. Journal f"ur die reine und angewandte Mathematik, 70:195-190, 1869. Google Scholar
  15. Eduardo Sany Laber, Ruy Luiz Milidiú, and Artur Alves Pessoa. On binary searching with non-uniform costs. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA., pages 855-864, 2001. Google Scholar
  16. Tak Wah Lam and Fung Ling Yue. Edge ranking of graphs is hard. Discrete Applied Mathematics, 85(1):71-86, 1998. Google Scholar
  17. Tak Wah Lam and Fung Ling Yue. Optimal edge ranking of trees in linear time. Algorithmica, 30(1):12-33, 2001. Google Scholar
  18. Nathan Linial and Michael E. Saks. Searching ordered structures. J. Algorithms, 6(1):86-103, 1985. Google Scholar
  19. Shay Mozes, Krzysztof Onak, and Oren Weimann. Finding an optimal tree searching strategy in linear time. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 1096-1105, 2008. Google Scholar
  20. Nils J. Nilsson. Problem-Solving Methods in Artificial Intelligence. McGraw-Hill Pub. Co., 1971. Google Scholar
  21. Robert Nowak. Noisy generalized binary search. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 1366-1374. Curran Associates, Inc., 2009. Google Scholar
  22. Krzysztof Onak and Pawel Parys. Generalization of binary search: Searching in trees and forest-like partial orders. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 379-388, 2006. Google Scholar
  23. Judea Pearl. Heuristics - intelligent search strategies for computer problem solving. Addison-Wesley series in artificial intelligence. Addison-Wesley, 1984. Google Scholar
  24. Andrzej Pelc. Searching games with errors - fifty years of coping with liars. Theor. Comput. Sci., 270(1-2):71-109, 2002. Google Scholar
  25. Alfred Renyi. On a problem in information theory. Magyar Tud. Akad. Mat. Kutato Int. Kozl, 6(B):505-516, 1961. Google Scholar
  26. Alejandro A. Sch"affer. Optimal node ranking of trees in linear time. Information Processing Letters, 33(2):91-96, 1989. Google Scholar
  27. Stanislaw Ulam. Adventures of a Mathematician. University of California Press, 1991. 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