[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Fast distributed algorithms for testing graph properties

  • Published:
Distributed Computing Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

We initiate a thorough study of distributed property testing—producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called dense graph testing model we emulate sequential tests for nearly all graph properties having 1-sided tests, while in the general model we obtain faster tests for triangle-freeness and cycle-freeness, and in the sparse model we obtain a faster test for bipartiteness. In addition, we show a logarithmic lower bound for testing bipartiteness and cycle-freeness, which holds even in the stronger LOCAL model. In most cases, aided by parallelism, the distributed algorithms have a much shorter running time than their counterparts from the sequential querying model of traditional property testing. More importantly, the distributed algorithms we develop for testing graph properties are in many cases much faster than what is known for exactly deciding whether the property holds. The simplest property testing algorithms allow a relatively smooth transition to the distributed model. For the more complex tasks we develop new machinery that may be of independent interest.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Here \(\tilde{\Omega }\) hides factors that are polylogarithmic in n.

  2. The probability of rejection can be improved by standard amplification techniques. In particular, the test can be repeated multiple times, and a vertex will reject if it rejects in any of the invocations.

  3. In the literature there are also investigations of a slightly strengthened general model, where pair queries are also allowed; its discussion is out of the scope for this paper.

  4. This technique was recently independently and concurrently devised in [20] for a different use.

  5. Sometimes in the sparse graph model the allowed number of changes is \(\epsilon dn\), as relates to the maximum possible number of edges; when d is held constant the difference is not essential.

  6. Pipelining means that each vertex has a buffer for each edge, which holds the information (edges between chosen vertices, in our case) it needs to send over that edge. The vertex sends the pieces of information one after the other.

  7. Note that the paths we address in this section are not necessarily simple.

  8. A more involved analysis of multiple prioritized BFS executions was used in [28], allowing all BFS executions to fully finish in a short time without too much delay due to congestion. Since we require a much weaker guarantee, we can avoid the strong full-fledged prioritization algorithm of [28] and settle for a simple rule that keeps one BFS tree alive. Also, the multiple BFS construction of [33] does not fit our demands as it may not reach all desired vertices within the required distance, in case there are many vertices that are closer.

  9. Our lower bound applies even to the less restricted LOCAL model of communication, which does not limit the size of the messages.

References

  1. Alon, N., Avin, C., Koucký, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many random walks are faster than one. Comb. Probab. Comput. 20(4), 481–502 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alon, N., Kaufman, T., Krivelevich, M., Ron, D.: Testing triangle-freeness in general graphs. SIAM J. Discrete Math. 22(2), 786–819 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alon, N., Krivelevich, M.: Testing k-colorability. SIAM J. Discrete Math. 15(2), 211–227 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  4. Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput. 37(6), 1703–1727 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  5. Arfaoui, H., Fraigniaud, P., Ilcinkas, D., Mathieu, F.: Distributedly testing cycle-freeness. In: Graph-Theoretic Concepts in Computer Science—40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25–27, 2014. Revised Selected Papers, pp. 15–28 (2014)

  6. Baruch, M., Fraigniaud, P., Patt-Shamir, B.: Randomized proof-labeling schemes. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21–23, 2015. pp. 315–324 (2015)

  7. Bender, M.A., Ron, D.: Testing properties of directed graphs: acyclicity and connectivity. Random Struct. Algorithms 20(2), 184–205 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  8. Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47(3), 549–595 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  9. Brakerski, Z., Patt-Shamir, B.: Distributed discovery of large near-cliques. Distrib. Comput. 24(2), 79–89 (2011)

    Article  MATH  Google Scholar 

  10. Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21–23, 2015. pp. 143–152 (2015)

  11. Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  12. Dolev, D., Lenzen, C., Peled, S.: “tri, tri again”: finding triangles and small subgraphs in a distributed setting-(extended abstract). In: Distributed Computing—26th International Symposium, DISC 2012, Salvador, Brazil, October 16–18, 2012. Proceedings. pp. 195–209 (2012)

  13. Drucker, A., Kuhn, F., Oshman, R.: The communication complexity of distributed task allocation. In: ACM Symposium on Principles of Distributed Computing, PODC ’12, Funchal, Madeira, Portugal, July 16–18, 2012. pp. 67–76 (2012)

  14. Drucker, Andrew, Kuhn, Fabian, Oshman, Rotem: On the power of the congested clique model. In ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014. pp. 367–376 (2014)

  15. Erdös, P.: Graph theory and probability. Can. J. Math. 11, 34G38 (1959)

    MathSciNet  Google Scholar 

  16. Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bull. EATCS 119. arXiv:1606.04434 [cs.DC] (2016)

  17. Fischer, E.: The art of uninformed decisions: a primer to property testing. Curr. Trends Theor. Compu. Sci. Chall. New Century I, 229–264 (2004)

    Article  MATH  Google Scholar 

  18. Foerster, K.-T., Luedi, T., Seidel, J., Wattenhofer, R.: Local checkability, no strings attached. In: Proceedings of the 17th International Conference on Distributed Computing and Networking, ICDCN 2016, Singapore, January 4–7, 2016. (2016)

  19. Fox, J.: A new proof of the graph removal lemma. CoRR. arXiv:1006.1300 (2010)

  20. Ghaffari, M., Kuhn, F., Su, H,-H.: Distributed MST and routing in almost mixing time. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 131–140 (2017)

  21. Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653–750 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  22. Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. Combinatorica 19(3), 335–373 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  23. Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32(2), 302–343 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  24. Goldreich, O., Ron, D.: Algorithmic aspects of property testing in the dense graphs model. In: Property Testing-Current Research and Surveys [outgrow of a workshop at the Institute for Computer Science (ITCS) at Tsinghua University, January 2010]. pp. 295–305 (2010)

  25. Goldreich, O., Trevisan, L.: Three theorems regarding testing graph properties. Random Struct. Algorithms 23(1), 23–57 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  26. Göös, M., Hirvonen, J., Levi, R., Medina, M., Suomela, J.: Non-local probes do not help with graph problems. CoRR. arxiv:1512.05411 (2015)

  27. Hirvonen, J., Rybicki, J., Schmid, S., Suomela, J.: Large cuts with local algorithms on triangle-free graphs. CoRR. arxiv:1402.2543 (2014)

  28. Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, PODC ’12. pp. 355–364. ACM, New York (2012)

  29. Izumi, T., Le Gall, F.: Triangle finding and listing in CONGEST networks. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25–27, 2017. pp. 381–389 (2017)

  30. Kari, J., Matamala, M., Rapaport, I., Salo, V.: Solving the induced subgraph problem in the randomized multiparty simultaneous messages model. In: Structural Information and Communication Complexity-22nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14–16, 2015, Post-proceedings. pp. 370–384 (2015)

  31. Kaufman, T., Krivelevich, M., Ron, D.: Tight bounds for testing bipartiteness in general graphs. SIAM J. Comput. 33(6), 1441–1483 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  32. Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215–233 (2010)

    Article  MATH  Google Scholar 

  33. Lenzen, C., Peleg, D.: Efficient distributed source detection with limited bandwidth. In: ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22–24, 2013. pp. 375–382 (2013)

  34. Mitzenmacher, M., Upfal, E.: Probability and Computing-Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)

    Book  MATH  Google Scholar 

  35. Parnas, M., Ron, D.: Testing the diameter of graphs. Random Struct. Algorithms 20(2), 165–183 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  36. Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theor. Comput. Sci. 381(1–3), 183–196 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  37. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)

    Book  MATH  Google Scholar 

  38. Pettie, S., Hsin-Hao, S.: Distributed coloring algorithms for triangle-free graphs. Inf. Comput. 243, 263–280 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  39. Ron, D.: Property testing: a learning theory perspective. Found. Trends Mach. Learn. 1(3), 307–402 (2008)

    Article  MATH  Google Scholar 

  40. Ron, D.: Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci. 5(2), 73–205 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  41. Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252–271 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  42. Sarma, A.D., Stephan, H., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235–1265 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  43. Sarma, A.D., Nanongkai, D., Pandurangan, G., Tetali, P.: Distributed random walks. J. ACM 60(1), 2 (2013)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel

    Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman & Yadu Vasudev

Authors
  1. Keren Censor-Hillel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eldar Fischer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gregory Schwartzman
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yadu Vasudev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Keren Censor-Hillel.

Additional information

A preliminary version of this work appeared in DISC 2016, pages 43–56.

Supported in part by the Israel Science Foundation (Grant 1696/14).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Censor-Hillel, K., Fischer, E., Schwartzman, G. et al. Fast distributed algorithms for testing graph properties. Distrib. Comput. 32, 41–57 (2019). https://doi.org/10.1007/s00446-018-0324-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-018-0324-8

Keywords