research-article

Deterministic and probabilistic binary search in graphs

Authors:

Ehsan Emamjomeh-Zadeh,

David Kempe,

Vikrant SinghalAuthors Info & Claims

STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

Pages 519 - 532

https://doi.org/10.1145/2897518.2897656

Published: 19 June 2016 Publication History

Get Access

Abstract

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₂ n queries are always sufficient. For general p, we give an (almost information-theoretically optimal) algorithm that uses, in expectation, no more than (1 − δ) logn/1 − H(p) + o(logn) + O(log² (1/δ)) queries, and identifies the target correctly with probability at leas 1 − δ. Here, H(p) = −(p logp + (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₂ 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 Σ_2k−1 in the polynomial hierarchy, and hardness for Σ_2k−5.

References

[1]

A. Abboud, A. Backurs, and V. Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proc. 56th IEEE Symp. on Foundations of Computer Science, 2015.

Abstract

References

Cited By

Index Terms

Recommendations

On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

Hardness of Approximation for Knapsack Problems

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations