### Deterministic and Probabilistic Binary Search in
Graphs

**Abstract:**

- Q: From San Diego?
- A: Straight East.
- Q: And what about Seattle?
- A: Southeast.
- Q: Hmm... Is it Dallas?

We consider the following natural generalization of Binary Search to
arbitrary connected graphs: 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 > 1/2 (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), log_{2} n queries are always sufficient. For general p,
we give an (information-theoretically optimal) algorithm that uses at most
(1 - δ) log n/(1 - H(p)) + o(log n) queries, and identifies the
target correctly with probability at least 1-δ. (Here, H(p) denotes
the entropy.)

We show several hardness results for the problem of determining, even
for p = 1, whether a target can always be found using K queries. Our upper
bound of log_{2} n implies a quasipolynomial-time algorithm for
undirected connected graphs; we show that this is best-possible under the
Strong Exponential Time Hypothesis. We show that for directed graphs, or
for undirected graphs with non-uniform node querying costs, the problem is
PSPACE-complete.