  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 > \frac{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
(almost information-theoretically optimal) algorithm that uses, in expectation,
no more than $(1 - \delta)\frac{\log_2 n}{1 - H(p)} + o(\log n) + O(\log^2
(1/\delta))$ queries, and identifies the target correctly with probability at
leas $1-\delta$. 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
$\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 (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 $\Sigma_{2k-1}$ in the polynomial hierarchy, and hardness
for $\Sigma_{2k-5}$.
