Binary Search in Graphs Revisited

DOI10.4230/LIPICS.MFCS.2017.20zbMATH Open1441.68028arXiv1702.08899OpenAlexW2897701371MaRDI QIDQ5111234FDOQ5111234

Argyrios Deligkas, P. G. Spirakis, George B. Mertzios

Publication date: 26 May 2020

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 $Gamma$ 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.

Full work available at URL: https://arxiv.org/abs/1702.08899

zbMATH Keywords

graphlower boundbinary searchprobabilistic algorithmapproximate query

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)

Cites Work

• Optimal node ranking of trees
• Computing with Noisy Information
• Edge ranking and searching in partial orders
• Optimal node ranking of tree in linear time
• The binary identification problem for weighted trees
• Searching ordered structures
• Optimal Search in Trees
• Sorting and Selection in Posets
• Searching games with errors -- fifty years of coping with liars
• On the complexity of searching in trees and partially ordered structures
• Edge ranking of graphs is hard
• Some Recent Results in Heuristic Search Theory
• On binary searching with non-uniform costs
• Optimal edge ranking of trees in linear time
• Deterministic and probabilistic binary search in graphs
• Searching a Tree with Permanently Noisy Advice
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• Binary search networks: A new method for key searching
• Semi-dynamic breadth-first search in digraphs
• Binary search and recursive graph problems
• Recontamination does not help to search a graph

This page was built for publication: Binary Search in Graphs Revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111234)