Abstract
We introduce the problem of augmenting graphs with sublinear memory in order to speed up replies to queries. As a concrete example, we focus on the following problem: the input is an (unpartitioned) bipartite graph \(G=(V,E)\). Given a query \(q \in V\), the algorithm’s goal is to output q’s color in some legal 2-coloring of G, using few probes to the graph. All replies have to be consistent with the same 2-coloring. We show that if a linear amount of preprocessing is allowed, there is a randomized algorithm that, for any \(\alpha \), uses \(O\left( \frac{m}{\alpha }\right) \) probes and \(\tilde{O}(\alpha )\) memory, where m is the number of edges in the graph. On the negative side, we show that for a natural family of algorithms that we call probe-first local computation algorithms, this trade-off is optimal even with unbounded preprocessing.
We describe a randomized algorithm that replies to queries using \(\tilde{O}\left( \frac{\sqrt{n}}{\varPhi ^2}\right) \) probes with no additional memory on regular graphs with conductance \(\varPhi \) (n is the number of vertices in G). In contrast, we show that any deterministic algorithm for regular graphs that uses no memory augmentation requires a linear (in n) number of probes, even if the conductance is the largest possible. We give an algorithm for grids and tori that uses a sublinear number of probes and no memory. Last, we give an algorithm for trees that errs on a sublinear number of edges (i.e., a sublinear number of edges are monochromatic under this coloring) that uses sublinear preprocessing, memory and probes per query.
Part of this work was done while the authors were visiting the Simons Institute for the Theory of Computing. Artur Czumaj was supported by the Centre for Discrete Mathematics and its Applications (DIMAP) and by EPSRC grant EP/N011163/1. Yishay Mansour was supported in part by the Israel Science Foundation (ISF). Shai Vardi was supported in part by the Linde Foundation and NSF grants CNS-1254169 and CNS-1518941.
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.
- 2.
Alternatively, it is known that we can define it as \(d_{TV}(\mu , \nu )=\frac{1}{2}\sum _{\sigma \in \varOmega } |\mu (\sigma )-\nu (\sigma )|\).
References
Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Property-preserving data reconstruction. Algorithmica 51(2), 160–182 (2008)
Aldous, D.J.: Random walks on finite groups and rapidly mixing Markov chains. Séminaire de probabilités de Strasbourg 17, 243–297 (1983). http://eudml.org/doc/113445
Alon, N., Rubinfeld, R., Vardi, S., Xie, N.: Space-efficient local computation algorithms. In: Proceedings of 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1132–1139 (2012)
Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9(1), 81–100 (1993)
Benczúr, A.A., Karger, D.R.: Approximating s-t minimum cuts in Õ(n2) time. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC 1996, pp. 47–55 (1996)
Chechik, S.: Approximate distance oracles with constant query time. In: Symposium on Theory of Computing, STOC, pp. 654–663 (2014)
Czumaj, A., Monemizadeh, M., Onak, K., Sohler, C.: Planar graphs: random walks and bipartiteness testing. In: Proceedings of 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 423–432 (2011)
Even, G., Medina, M., Ron, D.: Best of two local models: local centralized and local distributed algorithms. CoRR abs/1402.3796 (2014). http://arxiv.org/abs/1402.3796
Feige, U., Patt-Shamir, B., Vardi, S.: On the probe complexity of local computation algorithms. CoRR abs/1703.07734 (2017). http://arxiv.org/abs/1703.07734
Filtser, A., Solomon, S.: The greedy spanner is existentially optimal. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC, pp. 9–17 (2016)
Fraigniaud, P., Heinrich, M., Kosowski, A.: Local conflict coloring. In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pp. 625–634 (2016)
Fung, W.S., Hariharan, R., Harvey, N.J.A., Panigrahi, D.: A general framework for graph sparsification. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6–8 June 2011, pp. 71–80 (2011)
Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 270–277 (2016)
Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. Combinatorica 19(3), 335–373 (1999)
Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32(2), 302–343 (2002)
Göös, M., Hirvonen, J., Levi, R., Medina, M., Suomela, J.: Non-local probes do not help with many graph problems. In: Gavoille, C., Ilcinkas, D. (eds.) DISC 2016. LNCS, vol. 9888, pp. 201–214. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53426-7_15
Hassidim, A., Mansour, Y., Vardi, S.: Local computation mechanism design. ACM Trans. Econ. Comput. 4(4), 21:1–21:24 (2016). https://doi.org/10.1145/2956584
Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 80–86 (2000)
Kaufman, T., Krivelevich, M., Ron, D.: Tight bounds for testing bipartiteness in general graphs. SIAM J. Comput. 33(6), 1441–1483 (2004)
Lenzen, C., Levi, R.: A local algorithm for the sparse spanning graph problem. CoRR abs/1703.05418 (2017). http://arxiv.org/abs/1703.05418
Levi, R., Ron, D., Rubinfeld, R.: Local algorithms for sparse spanning graphs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, pp. 826–842 (2014)
Levi, R., Ron, D., Rubinfeld, R.: A local algorithm for constructing spanners in minor-free graphs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp. 38:1–38:15 (2016)
Levi, R., Rubinfeld, R., Yodpinyanee, A.: Brief announcement: local computation algorithms for graphs of non-constant degrees. In: Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA, pp. 59–61 (2015)
London, P., Chen, N., Vardi, S., Wierman, A.: Distributed optimization via local computation algorithms (2017). http://users.cms.caltech.edu/~plondon/loco.pdf
Mansour, Y., Patt-Shamir, B., Vardi, S.: Constant-time local computation algorithms. In: Sanità, L., Skutella, M. (eds.) WAOA 2015. LNCS, vol. 9499, pp. 110–121. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28684-6_10
Mansour, Y., Rubinstein, A., Vardi, S., Xie, N.: Converting online algorithms to local computation algorithms. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 653–664. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31594-7_55
Mansour, Y., Vardi, S.: A local computation approximation scheme to maximum matching. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX/RANDOM -2013. LNCS, vol. 8096, pp. 260–273. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40328-6_19
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2000)
Peleg, D., Schäffer, A.A.: Graph spanners. J. Graph Theory 13(1), 99–116 (1989)
Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510–530 (1989)
Reingold, O., Vardi, S.: New techniques and tighter bounds for local computation algorithms. J. Comput. Syst. Sci. 82(7), 1180–1200 (2016)
Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: Proceedings of 2nd Symposium on Innovations in Computer Science (ICS), pp. 223–238 (2011)
Saks, M.E., Seshadhri, C.: Local monotonicity reconstruction. SIAM J. Comput. 39(7), 2897–2926 (2010)
Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82(1), 93–133 (1989)
Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. SIAM J. Comput. 40(6), 1913–1926 (2011)
Thorup, M., Zwick, U.: Approximate distance oracles. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, (STOC), pp. 183–192 (2001)
Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA, pp. 1–10 (2001)
Wulff-Nilsen, C.: Approximate distance oracles with improved preprocessing time. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 202–208 (2012)
Yekhanin, S.: Locally decodable codes. Found. Trends Theor. Comput. Sci. 6(3), 139–255 (2012)
Acknowledgements
We thank the anonymous reviewers for their useful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Czumaj, A., Mansour, Y., Vardi, S. (2018). Sublinear Graph Augmentation for Fast Query Implementation. In: Epstein, L., Erlebach, T. (eds) Approximation and Online Algorithms. WAOA 2018. Lecture Notes in Computer Science(), vol 11312. Springer, Cham. https://doi.org/10.1007/978-3-030-04693-4_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-04693-4_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04692-7
Online ISBN: 978-3-030-04693-4
eBook Packages: Computer ScienceComputer Science (R0)