Document Open Access Logo

Three Notes on Distributed Property Testing

Authors Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, Ioan Todinca

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.15.pdf
  • Filesize: 0.87 MB
  • 30 pages

Document Identifiers

Author Details

Guy Even
Orr Fischer
Pierre Fraigniaud
Tzlil Gonen
Reut Levi
Moti Medina
Pedro Montealegre
Dennis Olivetti
Rotem Oshman
Ivan Rapaport
Ioan Todinca

Cite As Get BibTex

Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three Notes on Distributed Property Testing. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 15:1-15:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.15

Abstract

In this paper we present distributed property-testing algorithms for graph properties in the CONGEST model, with emphasis on testing subgraph-freeness. Testing a graph property P means distinguishing graphs G = (V,E) having property P from graphs that are epsilon-far from having it, meaning that epsilon|E| edges must be added or removed from G to obtain a graph satisfying P.

We present a series of results, including:

- Testing H-freeness in O(1/epsilon) rounds, for any constant-sized graph H containing an edge (u,v) such that any cycle in H contain either u or v (or both). This includes all connected graphs over five vertices except K_5. For triangles, we can do even better when epsilon is not too small.

- A deterministic CONGEST protocol determining whether a graph contains a given tree as a subgraph in constant time.

- For cliques K_s with s >= 5, we show that K_s-freeness can be tested in O(m^(1/2-1/(s-2)) epsilon^(-1/2-1/(s-2))) rounds, where m is the number of edges in the network graph.

- We describe a general procedure for converting epsilon-testers with f(D) rounds, where D denotes the diameter of the graph, to work in O((log n)/epsilon)+f((log n)/epsilon) rounds, where n is the number of processors of the network. We then apply this procedure to obtain an epsilon-tester for testing whether a graph is bipartite and testing whether a graph is cycle-free. Moreover, for cycle-freeness, we obtain a corrector of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property.

These protocols extend and improve previous results of [Censor-Hillel et al. 2016] and [Fraigniaud et al. 2016].

Subject Classification

Keywords
  • Property testing
  • Property correcting
  • Distributed algorithms
  • CONGEST model

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In 30th International Symposium in Distributed Computing (DISC), pages 29-42, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53426-7_3.
  2. Noga Alon, Sonny Ben-Shimon, and Michael Krivelevich. A note on regular ramsey graphs. Journal of Graph Theory, 64(3):244-249, 2010. Google Scholar
  3. Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient testing of large graphs. Combinatorica, 20(4):451-476, 2000. Google Scholar
  4. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  5. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  6. Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Low-diameter graph decomposition is in nc. In Scandinavian Workshop on Algorithm Theory, pages 83-93. Springer, 1992. Google Scholar
  7. Guy E Blelloch, Anupam Gupta, Ioannis Koutis, Gary L Miller, Richard Peng, and Kanat Tangwongsan. Nearly-linear work parallel sdd solvers, low-diameter decomposition, and low-stretch subgraphs. Theory of Computing Systems, 55(3):521-554, 2014. Google Scholar
  8. Luciana Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In 25th ACM Symposium on Principles of Database Systems (PODS), pages 253-262, 2006. Google Scholar
  9. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. In 30th Int. Symposium on Distributed Computing (DISC), volume 9888 of LNCS, pages 43-56. Springer, 2016. Google Scholar
  10. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In ACM Symposium on Principles of Distributed Computing (PODC), pages 143-152, 2015. Google Scholar
  11. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In 43rd ACM Symposium on Theory of Computing (STOC), pages 363-372, 2011. Google Scholar
  12. Danny Dolev, Christoph Lenzen, and Shir Peled. Tri, tri again: Finding triangles and small subgraphs in a distributed setting. In 26th International Symposium on Distributed Computing, pages 195-209, 2012. Google Scholar
  13. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In ACM Symposium on Principles of Distributed Computing (PODC), pages 367-376, 2014. Google Scholar
  14. Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 652-669. SIAM, 2017. Google Scholar
  15. Paul Erdős, András Hajnal, and J. W. Moon. A problem in graph theory. The American Mathematical Monthly, 71(10):1107-1110, 1964. Google Scholar
  16. Guy Even, Reut Levi, and Moti Medina. Faster and simpler distributed algorithms for testing and correcting graph properties in the congest-model. CoRR, abs/1705.04898, 2017. URL: http://arxiv.org/abs/1705.04898.
  17. Orr Fischer, Tzlil Gonen, and Rotem Oshman. Distributed property testing for subgraph-freeness revisited. CoRR, abs/1705.04033, 2017. URL: http://arxiv.org/abs/1705.04033.
  18. Pierre Fraigniaud, Pedro Montealegre, Dennis Olivetti, Ivan Rapaport, and Ioan Todinca. Distributed subgraph detection. CoRR, abs/1706.03996, 2017. URL: http://arxiv.org/abs/1706.03996.
  19. Pierre Fraigniaud and Dennis Olivetti. Distributed detection of cycles. In 29th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017. Google Scholar
  20. Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed testing of excluded subgraphs. In 30th Int. Symposium on Distributed Computing (DISC), volume 9888 of LNCS, pages 342-356. Springer, 2016. Google Scholar
  21. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1150-1162, 2012. Google Scholar
  22. Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653-750, 1998. Google Scholar
  23. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. Google Scholar
  24. Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In ACM Symposium on Principles of Distributed Computing (PODC), pages 355-364, 2012. URL: http://dx.doi.org/10.1145/2332432.2332504.
  25. Kazuo Iwama and Yuichi Yoshida. Parameterized testability. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 507-516, 2014. URL: http://dx.doi.org/10.1145/2554797.2554843.
  26. Taisuke Izumi and François Le Gall. Triangle finding and listing in CONGEST networks. In ACM Symposium on Principles of Distributed Computing (PODC), 2017. Google Scholar
  27. Stasys Jukna and Georg Schnitger. Triangle-freeness is hard to detect. Combinatorics, Probability, &Computing, 11(6):549-569, 2002. Google Scholar
  28. Shay Kutten and David Peleg. Fast distributed construction of small k-dominating sets and applications. J. Algorithms, 28(1):40-66, 1998. URL: http://dx.doi.org/10.1006/jagm.1998.0929.
  29. Tom Leighton. Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann, 1992. Google Scholar
  30. Christoph Lenzen and Boaz Patt-Shamir. Fast partial distance estimation and applications. In ACM Symposium on Principles of Distributed Computing (PODC), pages 153-162, 2015. URL: http://dx.doi.org/10.1145/2767386.2767398.
  31. Gary L Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures, pages 196-203. ACM, 2013. Google Scholar
  32. Burkhard Monien. How to find long paths efficiently. In Analysis and design of algorithms for combinatorial problems, volume 109 of North-Holland Math. Stud., pages 239-254. North-Holland, Amsterdam, 1985. URL: http://dx.doi.org/10.1016/S0304-0208(08)73110-4.
  33. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In ACM Symposium on Theory of Computing (STOC), pages 565-573, 2014. URL: http://dx.doi.org/10.1145/2591796.2591850.
  34. Hiroaki Ookawa and Taisuke Izumi. Filling logarithmic gaps in distributed complexity for global problems. In 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 377-388, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46078-8_31.
  35. Judea Pearl. Fusion, propagation, and structuring in belief networks. Artif. Intell., 29(3):241-288, 1986. Google Scholar
  36. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact