Binary Search in Graphs
Ehsan Emamjomeh-Zadeh, David Kempe · arXiv (Cornell University) · 2015
We study the following natural generalization of Binary Search to arbitrary connected graphs and nite metric spaces. In a given and known 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. Our main positive result is that in graphs, and hence in nite metrics, log 2 n queries are always sucient to nd the target. This result extends to directed graphs that are \almost undirected in the sense that each edge e with weight !e is part of a cycle of total weight at most c !e: here, c ln(n) queries are sucient. On the negative side, for strongly connected directed graphs, deciding whether K queries are sucient to identify the target is PSPACE-complete. This result also applies to graphs with non-uniform query costs. We also show hardness in the polynomial hierarchy for a \semi-adaptive version of the problem: the algorithm gets to query r vertices each in k rounds. This version is 2k 5-hard and in 2k 1 in the polynomial hierarchy.