An Efficient Noisy Binary Search in Graphs via Median Approximation

Dariusz Dereniowski; Aleksander Łukasiewicz; Przemysław Uznański

doi:10.1007/978-3-030-79987-8_19

An Efficient Noisy Binary Search in Graphs via Median Approximation

Abstract

Consider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a strategy, that identifies an initially unknown target vertex in a graph by asking queries. Each query is conducted as follows: the strategy selects a vertex q and receives a reply v: if q is the target, then =, and if q is not the target, then v is a neighbor of q that lies on a shortest path to the target. Furthermore, there is a noise parameter 0≤<12 which means that each reply can be incorrect with probability p. The optimization criterion to be minimized is the overall number of queries asked by the strategy, called the query complexity. The query complexity is well understood to be O(ε−2log) for general graphs, where n is the order of the graph and ε=1/2−. However, implementing such a strategy is computationally expensive, with each query requiring possibly O(^2) operations. In this work we propose two efficient strategies that keep the optimal query complexity. The first strategy achieves the overall complexity of O(ε−1log) per a single query. The second strategy is dedicated to graphs of small diameter D and maximum degree Δ and has the average complexity of O(+ε−2Δlog) per query. We point out that we develop an algorithmic tool of graph median approximation that is of independent interest: the median can be efficiently approximated by finding a vertex minimizing the sum of distances to a randomly sampled vertex subset of size O(ε−2log).

Citations

3

CrossRef
0

Web of Science
6

Scopus

Authors (3)

Dariusz Dereniowski prof. dr hab. inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Aleksander Łukasiewicz
- Uniwersytet Wrocławski
Przemysław Uznański
- Uniwersytet Wrocławski

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:

Conference activity

Type:

publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)

Published in:

LECTURE NOTES IN COMPUTER SCIENCE no. 12757, pages 265 - 281,
ISSN: 0302-9743

Title of issue:

Combinatorial Algorithms strony 265 - 281

Language:

English

Publication year:

2021

Bibliographic description:

Dereniowski D., Łukasiewicz A., Uznański P.: An Efficient Noisy Binary Search in Graphs via Median Approximation// Combinatorial Algorithms/ : , 2021, s.265-281

DOI: