A. Deligkas
Binary search in graphs revisited
Deligkas, A.; Mertzios, G.B.; Spirakis, P.G.
Authors
Contributors
Kim G. Larsen
Editor
Hans L. Bodlaender
Editor
Jean-Francois Raskin
Editor
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.
Citation
Deligkas, A., Mertzios, G., & Spirakis, P. (2017). Binary search in graphs revisited. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.20
Conference Name | 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS) |
---|---|
Conference Location | Aalborg, Denmark |
Start Date | Aug 21, 2017 |
End Date | Aug 25, 2017 |
Acceptance Date | Jun 12, 2017 |
Publication Date | Dec 1, 2017 |
Deposit Date | Jun 26, 2017 |
Publicly Available Date | Mar 28, 2024 |
Series Title | LIPIcs–Leibniz International Proceedings in Informatics |
Series Number | 83 |
Series ISSN | 1868-8969 |
Book Title | 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings |
DOI | https://doi.org/10.4230/lipics.mfcs.2017.20 |
Public URL | https://durham-repository.worktribe.com/output/1146773 |
Files
Accepted Conference Proceeding
(480 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Argyrios Deligkas, George B. Mertios, Paul G. Spirakis;
licensed under Creative Commons License CC-BY
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search