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 \(v=q\), 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\le p<\frac{1}{2}\) 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 \(\mathcal {O}(\varepsilon ^{-2}\log n)\) for general graphs, where n is the order of the graph and \(\varepsilon =\frac{1}{2}\,-\,p\). However, implementing such a strategy is computationally expensive, with each query requiring possibly \(\mathcal {O}(n^2)\) operations.
In this work we propose two efficient strategies that keep the optimal query complexity. The first strategy achieves the overall complexity of \(\mathcal {O}(\varepsilon ^{-1}n\log n)\) per a single query. The second strategy is dedicated to graphs of small diameter D and maximum degree \(\varDelta \) and has the average complexity of \(\mathcal {O}(n+\varepsilon ^{-2}D\varDelta \log n)\) 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 \(\mathcal {O}(\varepsilon ^{-2}\log n)\).
Partially supported by National Science Centre (Poland) grant number 2018/31/B/ST6/00820.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We note that such an erroneous reply may occur both when \(v^{*}=q\) and \(v^{*}\ne q\).
- 2.
By information-theoretic arguments, any algorithm that locates the target correctly with probability \(1-\delta \) has to make \(\frac{\log _2 n}{1-H(p)} + \varOmega (\frac{\log \delta ^{-1}}{1-H(p)})\) queries. In the regime of high probability algorithms this becomes simply \(\varOmega (\frac{\log n}{\varepsilon ^2})\) queries.
- 3.
Actually, our method is slightly more general: our proofs reveal that the algorithm is resilient to the placement of errors, and it will succeed if at most a p-fraction of replies is erroneous, which makes it usable against users that distribute lies adversarially.
References
Abboud, A., Grandoni, F., Williams, V.V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: SODA 2015, pp. 1681–1697 (2015). https://doi.org/10.1137/1.9781611973730.112
Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: SODA 2016, pp. 377–391 (2016). https://doi.org/10.1137/1.9781611974331.ch28
Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension and provably efficient shortest path algorithms. J. ACM 63(5), 41:1–41:26 (2016). https://doi.org/10.1145/2985473
Aigner, M.: Searching with lies. J. Comb. Theory Ser. A 74(1), 43–56 (1996). https://doi.org/10.1006/jcta.1996.0036
Bavelas, A.: Communication patterns in task-oriented groups. J. Acoust. Soc. Am. 22(6), 725–730 (1950). https://doi.org/10.1121/1.1906679
Beauchamp, M.A.: An improved index of centrality. Behav. Sci. 10(2), 161–163 (1965). https://doi.org/10.1002/bs.3830100205
Ben-Asher, Y., Farchi, E., Newman, I.: Optimal search in trees. SIAM J. Comput. 28(6), 2090–2102 (1999). https://doi.org/10.1137/S009753979731858X
Ben-Or, M., Hassidim, A.: The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well). In: FOCS 2008, pp. 221–230 (2008). https://doi.org/10.1109/FOCS.2008.58
Bénéteau, L., Chalopin, J., Chepoi, V., Vaxès, Y.: Medians in median graphs in linear time. CoRR abs/1907.10398 (2019)
Boczkowski, L., Korman, A., Rodeh, Y.: Searching a tree with permanently noisy advice. In: ESA 2018, pp. 54:1–54:13 (2018). https://doi.org/10.4230/LIPIcs.ESA.2018.54
Borgstrom, R.S., Kosaraju, S.R.: Comparison-based search in the presence of errors. In: STOC 1993, pp. 130–136 (1993). https://doi.org/10.1145/167088.167129
Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. In: SODA 2017, pp. 2143–2152 (2017). https://doi.org/10.1137/1.9781611974782.139
Cantone, D., Cincotti, G., Ferro, A., Pulvirenti, A.: An efficient approximate algorithm for the 1-median problem in metric spaces. SIAM J. Optim. 16(2), 434–451 (2005). https://doi.org/10.1137/S1052623403424740
Chang, C.: Some results on approximate 1-median selection in metric spaces. Theor. Comput. Sci. 426, 1–12 (2012). https://doi.org/10.1016/j.tcs.2011.12.003
Chechik, S., Cohen, E., Kaplan, H.: Average distance queries through weighted samples in graphs and metric spaces: high scalability with tight statistical guarantees. In: APPROX-RANDOM 2015, pp. 659–679 (2015). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.659
Dagan, Y., Filmus, Y., Gabizon, A., Moran, S.: Twenty (simple) questions. In: STOC 2017, pp. 9–21 (2017). https://doi.org/10.1145/3055399.3055422
Deligkas, A., Mertzios, G.B., Spirakis, P.G.: Binary search in graphs revisited. Algorithmica 81(5), 1757–1780 (2018). https://doi.org/10.1007/s00453-018-0501-y
Dereniowski, D.: Edge ranking and searching in partial orders. Discret. Appl. Math. 156(13), 2493–2500 (2008). https://doi.org/10.1016/j.dam.2008.03.007
Dereniowski, D., Kosowski, A., Uznański, P., Zou, M.: Approximation strategies for generalized binary search in weighted trees. In: ICALP 2017, pp. 84:1–84:14 (2017). https://doi.org/10.4230/LIPIcs.ICALP.2017.84
Dereniowski, D., Tiegel, S., Uznański, P., Wolleb-Graf, D.: A framework for searching in graphs in the presence of errors. In: SOSA@SODA 2019, pp. 4:1–4:17 (2019). https://doi.org/10.4230/OASIcs.SOSA.2019.4
Dhagat, A., Gács, P., Winkler, P.: On playing “twenty questions” with a liar. In: SODA 1992, pp. 16–22 (1992)
Emamjomeh-Zadeh, E., Kempe, D.: A general framework for robust interactive learning. In: NIPS 2017, pp. 7085–7094 (2007)
Emamjomeh-Zadeh, E., Kempe, D., Singhal, V.: Deterministic and probabilistic binary search in graphs. In: STOC 2016, pp. 519–532 (2016). https://doi.org/10.1145/2897518.2897656
Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001–1018 (1994). https://doi.org/10.1137/S0097539791195877
Freeman, L.C.: Centrality in social networks conceptual clarification. Soc. Netw. 1(3), 215–239 (1978)
Gavoille, C., Peleg, D., Pérennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85–112 (2004). https://doi.org/10.1016/j.jalgor.2004.05.002
Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 12(3), 450–459 (1964)
Indyk, P.: Sublinear time algorithms for metric space problems. In: STOC 1999, pp. 428–434 (1999). https://doi.org/10.1145/301250.301366
Karp, R.M., Kleinberg, R.: Noisy binary search and its applications. In: SODA 2007, pp. 881–890 (2007)
Kosowski, A., Viennot, L.: Beyond highway dimension: Small distance labels using tree skeletons. In: SODA 2017, pp. 1462–1478 (2017). https://doi.org/10.1137/1.9781611974782.95
Lam, T.W., Yue, F.L.: Optimal edge ranking of trees in linear time. Algorithmica 30(1), 12–33 (2001). https://doi.org/10.1007/s004530010076
Mozes, S., Onak, K., Weimann, O.: Finding an optimal tree searching strategy in linear time. In: SODA 2008, pp. 1096–1105 (2008)
Onak, K., Parys, P.: Generalization of binary search: searching in trees and forest-like partial orders. In: FOCS 2006, pp. 379–388 (2006). https://doi.org/10.1109/FOCS.2006.32
Ostresh, L.M.: On the convergence of a class of iterative methods for solving the weber location problem. Oper. Res. 26(4), 597–609 (1978). https://doi.org/10.1287/opre.26.4.597
Rivest, R.L., Meyer, A.R., Kleitman, D.J., Winklmann, K., Spencer, J.: Coping with errors in binary search procedures. J. Comput. Syst. Sci. 20(3), 396–404 (1980). https://doi.org/10.1016/0022-0000(80)90014-8
Rényi, A.: On a problem of information theory. MTA Mat. Kut. Int. Kozl. 6B, 505–516 (1961)
Sabidussi, G.: The centrality index of a graph. Psychometrika 31(4), 581–603 (1966). https://doi.org/10.1007/bf02289527
Schäffer, A.A.: Optimal node ranking of trees in linear time. Inf. Process. Lett. 33(2), 91–96 (1989). https://doi.org/10.1016/0020-0190(89)90161-0
Tabata, K., Nakamura, A., Kudo, M.: Fast approximation algorithm for the 1-median problem. In: Ganascia, J.-G., Lenca, P., Petit, J.-M. (eds.) DS 2012. LNCS (LNAI), vol. 7569, pp. 169–183. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33492-4_15
Tabata, K., Nakamura, A., Kudo, M.: An efficient approximate algorithm for the 1-median problem on a graph. IEICE Trans. Inf. Syst. 100–D(5), 994–1002 (2017). https://doi.org/10.1587/transinf.2016EDP7398
Tansel, B.C., Francis, R.L., Lowe, T.J.: State of the art-location on networks: a survey. Part I: the p-center and p-median problems. Manag. Sci. 29(4), 482–497 (1983)
Ulam, S.M.: Adventures of a Mathematician. Scribner, New York (1976)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Dereniowski, D., Łukasiewicz, A., Uznański, P. (2021). An Efficient Noisy Binary Search in Graphs via Median Approximation. In: Flocchini, P., Moura, L. (eds) Combinatorial Algorithms. IWOCA 2021. Lecture Notes in Computer Science(), vol 12757. Springer, Cham. https://doi.org/10.1007/978-3-030-79987-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-79987-8_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-79986-1
Online ISBN: 978-3-030-79987-8
eBook Packages: Computer ScienceComputer Science (R0)