Deterministic and probabilistic binary search in graphs

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 > 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 − δ) log n /1 − H ( p ) + o (log n ) + O (log 2 (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 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 Σ 2 k −1 in the polynomial hierarchy, and hardness for Σ 2 k −5 .

Authors

• Ehsan Emamjomeh-Zadeh
• David Kempe 0001
• Vikrant Singhal

Keywords

• Exponential-Time Hypothesis
• Noisy Binary Search
• PSPACE-hardness
• Quasipolynomial-Time Algorithms
• Searching in Metric Spaces