Deterministic and probabilistic binary search in graphs

DOI10.1145/2897518.2897656MaRDI QIDQ5361858zbMATH OpenOpenAlexFDO

Authors Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.00805

zbMATH Keywords

exponential-time hypothesisnoisy binary searchPSPACE-hardnessquasipolynomial-time algorithmssearching in metric spaces

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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>frac12$ (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), $lo{g}_{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)fraclo{g}_{2}n1-H(p)+o(logn)+O(lo{g}^2(1/delta))$ queries, and identifies the target correctly with probability at leas $1-delta$. Here, $H(p)=-(plogp+(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 $lo{g}_{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 $Sigm{a}_{2k-1}$ in the polynomial hierarchy, and hardness for $Sigm{a}_{2k-5}$.

Recommendations

• Binary search in graphs revisited
• Binary search in graphs revisited
• Approximation strategies for generalized binary search in weighted trees
• On the complexity of searching in trees: average-case minimization
• A binary search problem on graphs

Cited in

(33)

• Binary search and recursive graph problems
• Binary search in graphs revisited
• On the diameter of tree associahedra
• An efficient noisy binary search in graphs via Median approximation
• The power of adaptivity in source identification with time queries on the path
• Path search in the pyramid and in other graphs
• Identifying codes and searching with balls in graphs
• An almost-greedy search on random binary vectors and random graphs
• Bisection search with noisy responses
• Noisy binary search and its applications
• Constrained binary identification problem
• Deterministic Decentralized Search in Random Graphs
• On the Complexity of Finding an Unknown Cut Via Vertex Queries
• Searching a Tree with Permanently Noisy Advice
• Sequential metric dimension for random graphs
• The tree search game for two players
• Binary search in graphs revisited
• Search for the end of a path in the \(\cdot\)-dimensional grid and in other graphs
• The complexity of bicriteria tree-depth
• Competitive Online Search Trees on Trees
• Theoretical analysis of git bisect
• Edge and pair queries-random graphs and complexity
• Theoretical Analysis of Git Bisect
• Partial order multiway search
• A framework for searching in graphs in the presence of errors
• Sharp noisy binary search with monotonic probabilities
• The query complexity of searching trees with permanently noisy advice
• Combinatorial generation via permutation languages. IV: Elimination trees
• Interactive learning of a dynamic structure
• Learning with comparison feedback: online estimation of sample statistics
• Noisy (binary) searching: simple, fast and correct
• Computational geometry with probabilistically noisy primitive operations
• Randomized binary and tree search under pressure

This page was built for publication: Deterministic and probabilistic binary search in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361858)