Dereniowski, Dariusz ;
Tiegel, Stefan ;
Uznanski, Przemyslaw ;
WollebGraf, Daniel
A Framework for Searching in Graphs in the Presence of Errors
Abstract
We consider a problem of searching for an unknown target vertex t in a (possibly edgeweighted) graph. Each vertexquery points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by EmamjomehZadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the errorless case and for the independent noise model (where each query independently receives an erroneous answer with known probability p<1/2 and a correct one with probability 1p).
We study this problem both with adversarial errors and independent noise models. First, we show an algorithm that needs at most (log_2 n)/(1  H(r)) queries in case of adversarial errors, where the adversary is bounded with its rate of errors by a known constant r<1/2. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking an amortization argument. We then show that our algorithm coupled with a Chernoff bound argument leads to a simpler algorithm for the independent noise model and has a query complexity that is both simpler and asymptotically better than the one of EmamjomehZadeh et al. [STOC 2016].
Our approach has a wide range of applications. First, it improves and simplifies the Robust Interactive Learning framework proposed by EmamjomehZadeh and Kempe [NIPS 2017]. Secondly, performing analogous analysis for edgequeries (where a query to an edge e returns its endpoint that is closer to the target) we actually recover (as a special case) a noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon an algorithm for searching of unbounded domains due to Aslam and Dhagat [STOC 1991].
BibTeX  Entry
@InProceedings{dereniowski_et_al:OASIcs:2018:10030,
author = {Dariusz Dereniowski and Stefan Tiegel and Przemyslaw Uznanski and Daniel WollebGraf},
title = {{A Framework for Searching in Graphs in the Presence of Errors}},
booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
pages = {4:14:17},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783959770996},
ISSN = {21906807},
year = {2018},
volume = {69},
editor = {Jeremy T. Fineman and Michael Mitzenmacher},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10030},
URN = {urn:nbn:de:0030drops100305},
doi = {10.4230/OASIcs.SOSA.2019.4},
annote = {Keywords: graph algorithms, noisy binary search, query complexity, reliability}
}
08.01.2019
Keywords: 

graph algorithms, noisy binary search, query complexity, reliability 
Seminar: 

2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Issue date: 

2018 
Date of publication: 

08.01.2019 