A. Deligkas
Binary search in graphs revisited
Deligkas, A.; Mertzios, G.B.; Spirakis, P.G.
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. (in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC 2016, Cambridge, pp. 519–532, 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 Φ 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 Γ that allows querying approximate medians.
Citation
Deligkas, A., Mertzios, G., & Spirakis, P. (2019). Binary search in graphs revisited. Algorithmica, 81(5), Article 1757. https://doi.org/10.1007/s00453-018-0501-y
Journal Article Type | Article |
---|---|
Acceptance Date | Aug 4, 2018 |
Online Publication Date | Aug 22, 2018 |
Publication Date | May 31, 2019 |
Deposit Date | Aug 16, 2018 |
Publicly Available Date | Sep 19, 2018 |
Journal | Algorithmica |
Print ISSN | 0178-4617 |
Electronic ISSN | 1432-0541 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 81 |
Issue | 5 |
Article Number | 1757 |
DOI | https://doi.org/10.1007/s00453-018-0501-y |
Public URL | https://durham-repository.worktribe.com/output/1322744 |
Related Public URLs | https://arxiv.org/abs/1702.08899 |
Files
Published Journal Article
(557 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Published Journal Article (Advance online version)
(567 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
Advance online version © The Author(s) 2018 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
You might also like
The complexity of computing optimum labelings for temporal connectivity
(2022)
Presentation / Conference Contribution
The complexity of temporal vertex cover in small-degree graphs
(2022)
Presentation / Conference Contribution
The complexity of transitively orienting temporal graphs
(2021)
Presentation / Conference Contribution
Equitable scheduling on a single machine
(2021)
Presentation / Conference Contribution
Exact and approximate algorithms for computing a second Hamiltonian cycle
(2020)
Presentation / Conference Contribution
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