Document Open Access Logo

Testable Bounded Degree Graph Properties Are Random Order Streamable

Authors Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, Christian Sohler

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.131.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Morteza Monemizadeh
S. Muthukrishnan
Pan Peng
Christian Sohler

Cite As Get BibTex

Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler. Testable Bounded Degree Graph Properties Are Random Order Streamable. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 131:1-131:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.131

Abstract

We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in a single-pass in random order streams. Our result is obtained by estimating the distribution of local neighborhoods of the vertices on a random order graph stream using constant space.

We then show that our approach can also be applied to constant time approximation algorithms for bounded degree graphs in the adjacency list model: As an example, we obtain a constant-space single-pass random order streaming algorithms for approximating the size of a maximum matching with additive error epsilon n (n is the number of nodes). 

Our result establishes for the first time that a large class of sublinear algorithms can be simulated in random order streams, while Omega(n) space is needed for many graph streaming problems for adversarial orders.

Subject Classification

Keywords
  • Graph streaming algorithms
  • graph property testing
  • constant-time approximation algorithms

Metrics

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

References

  1. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20-29. ACM, 1996. Google Scholar
  2. Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1723-1742. SIAM, 2017. Google Scholar
  3. Itai Benjamini, Oded Schramm, and Asaf Shapira. Every minor-closed property of sparse graphs is testable. Advances in mathematics, 223(6):2200-2218, 2010. Google Scholar
  4. Marc Bury and Chris Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data streams. In Algorithms-ESA 2015, pages 263-274. Springer, 2015. Google Scholar
  5. Amit Chakrabarti, Graham Cormode, and Andrew McGregor. Robust lower bounds for communication and stream computation. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 641-650. ACM, 2008. Google Scholar
  6. Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput., 34(6):1370-1379, 2005. Google Scholar
  7. Artur Czumaj, Pan Peng, and Christian Sohler. Relating two property testing models for bounded degree directed graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 1033-1045. ACM, 2016. Google Scholar
  8. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2-3):207-216, 2005. Google Scholar
  9. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM Journal on Computing, 38(5):1709-1727, 2008. Google Scholar
  10. Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. Testing and spot-checking of data streams. Algorithmica, 34(1):67-80, 2002. Google Scholar
  11. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. Google Scholar
  12. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32:302-343, 2002. Google Scholar
  13. Oded Goldreich and Dana Ron. On proximity-oblivious testing. SIAM Journal on Computing, 40(2):534-566, 2011. Google Scholar
  14. Oded Goldreich and Luca Trevisan. Three theorems regarding testing graph properties. Random Structures &Algorithms, 23(1):23-57, 2003. Google Scholar
  15. Avinatan Hassidim, Jonathan A Kelner, Huy N Nguyen, and Krzysztof Onak. Local graph partitions for approximation and testing. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 22-31. IEEE, 2009. Google Scholar
  16. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. Computing on data streams. In External Memory Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, May 20-22, 1998, pages 107-118, 1998. Google Scholar
  17. Zengfeng Huang and Pan Peng. Dynamic graph stream algorithms in o(n) space. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 18:1-18:16, 2016. Google Scholar
  18. Hiro Ito, Shin-Ichi Tanigawa, and Yuichi Yoshida. Constant-time algorithms for sparsity matroids. In International Colloquium on Automata, Languages, and Programming, pages 498-509. Springer, 2012. Google Scholar
  19. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from random streams. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 734-751. Society for Industrial and Applied Mathematics, 2014. Google Scholar
  20. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating max-cut. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1263-1282. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  21. Ken-ichi Kawarabayashi and Yuichi Yoshida. Testing subdivision-freeness: property testing meets structural graph theory. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 437-446. ACM, 2013. Google Scholar
  22. Christian Konrad, Frédéric Magniez, and Claire Mathieu. Maximum matching in semi-streaming with few passes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 231-242. Springer, 2012. Google Scholar
  23. Sharon Marko and Dana Ron. Approximating the distance to properties in bounded-degree and general sparse graphs. ACM Transactions on Algorithms (TALG), 5(2):22, 2009. Google Scholar
  24. Andrew McGregor. Graph stream algorithms: a survey. ACM SIGMOD Record, 43(1):9-20, 2014. Google Scholar
  25. Ilan Newman and Christian Sohler. Every property of hyperfinite graphs is testable. SIAM Journal on Computing, 42(3):1095-1112, 2013. Google Scholar
  26. Huy N Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 327-336. IEEE, 2008. Google Scholar
  27. Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1123-1131. SIAM, 2012. Google Scholar
  28. Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science, 381(1):183-196, 2007. Google Scholar
  29. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  30. Xiaoming Sun and David P Woodruff. Tight bounds for graph problems in insertion streams. In LIPIcs-Leibniz International Proceedings in Informatics, volume 40. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  31. Shin-Ichi Tanigawa and Yuichi Yoshida. Testing the supermodular-cut condition. Algorithmica, 71(4):1065-1075, 2015. Google Scholar
  32. Elad Verbin and Wei Yu. The streaming complexity of cycle counting, sorting by reversals, and other problems. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 11-25. SIAM, 2011. Google Scholar
  33. Yuichi Yoshida and Hiro Ito. Property testing on k-vertex-connectivity of graphs. In Automata, Languages and Programming, pages 539-550. Springer, 2008. Google Scholar
  34. Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM J. Comput., 41(4):1074-1093, 2012. 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