# Deterministic and Probabilistic Binary Search in Graphs

arXiv: https://arxiv.org/abs/1503.00805 · HTML: https://mlsanity.com/paper/1503.00805/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2015.

## Built on by (most cited first, 6 of 6)

- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)
- [Learning with Comparison Feedback: Online Estimation of Sample Statistics](https://mlsanity.com/paper/2101.04176/) (2021)
- [Sharp Noisy Binary Search with Monotonic Probabilities](https://mlsanity.com/paper/2311.00840/) (2023)
- [Precedence-Constrained Decision Trees and Coverings](https://mlsanity.com/paper/2602.21312/) (2026)
- [Active Seriation: Efficient Ordering Recovery with Statistical Guarantees](https://mlsanity.com/paper/2603.15336/) (2026)
- [A Unified Analysis of Dynamic Interactive Learning](https://mlsanity.com/paper/2204.07071/) (2022)

## Abstract (arXiv)

We consider the following natural generalization of Binary Search: in a given undirected, positively weighted graph, one vertex is a target. The algorithm's task is to identify the target by adaptively querying vertices. In response to querying a node q, the algorithm learns either that q is the target, or is given an edge out of q that lies on a shortest path from q to the target. We study this problem in a general noisy model in which each query independently receives a correct answer with probability p > frac12 (a known constant), and an (adversarial) incorrect one with probability 1-p. Our main positive result is that when p = 1 (i.e., all answers are correct), log2 n queries are always sufficient. For general p, we give an (almost information-theoretically optimal) algorithm that uses, in expectation, no more than (1 - δ)fraclog2 n1 - H(p) + o(log n) + O(log2 (1/δ)) queries, and identifies the target correctly with probability at leas 1-δ. Here, H(p) = -(p log p + (1-p) log(1-p)) denotes the entropy. The first bound is achieved by the algorithm that iteratively queries a 1-median of the nodes not ruled out yet; the second bound by careful repeated invocations of a multiplicative weights algorithm. Even for p = 1, we show several hardness results for the problem of determining whether a target can be found using K queries. Our upper bound of log2 n implies a quasipolynomial-time algorithm for undirected connected graphs; we show that this is best-possible under the Strong Exponential Time Hypothesis (SETH). Furthermore, for directed graphs, or for undirected graphs with non-uniform node querying costs, the problem is PSPACE-complete. For a semi-adaptive version, in which one may query r nodes each in k rounds, we show membership in Sigma2k-1 in the polynomial hierarchy, and hardness for Sigma2k-5.