Document Open Access Logo

The Subgraph Testing Model

Authors Oded Goldreich, Dana Ron

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.37.pdf
  • Filesize: 448 kB
  • 19 pages

Document Identifiers

Author Details

Oded Goldreich
  • Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
Dana Ron
  • School of Electrical Engineering, Tel Aviv University, Tel Aviv, Israel

Funding

This research was partially supported by the Israel Science Foundation (grants No. 671/13 and 1146/18).

Cite AsGet BibTex

Oded Goldreich and Dana Ron. The Subgraph Testing Model. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.37

Abstract

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph. The tester is given free access to a base graph G=([n],E), and oracle access to a function f:E -> {0,1} that represents a subgraph of G. The tester is required to distinguish between subgraphs that posses a predetermined property and subgraphs that are far from possessing this property. We focus on bounded-degree base graphs and on the relation between testing graph properties in the subgraph model and testing the same properties in the bounded-degree graph model. We identify cases in which testing is significantly easier in one model than in the other as well as cases in which testing has approximately the same complexity in both models. Our proofs are based on the design and analysis of efficient testers and on the establishment of query-complexity lower bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Property Testing
  • Graph Properties

Metrics

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

References

  1. N. Alon, P.D. Seymour, and R. Thomas. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC), pages 293-299, 1990. Google Scholar
  2. E. Ben-Sasson, P. Harsha, and S. Raskhodnikova. 3CNF properties are hard to test. SIAM Journal on Computing, 35(1):1-21, 2005. Google Scholar
  3. I. Benjamini, O. Schramm, and A. Shapira. Every minor-closed property of sparse graphs is testable. Advances in mathematics, 223:2200-2218, 2010. Google Scholar
  4. A. Bogdanov, K. Obata, and L. Trevisan. A lower bound for testing 3-colorability in bounded-degree graphs. In Proceedings of the Forty-Third Annual Symposium on Foundations of Computer Science (FOCS), pages 93-102, 2002. Google Scholar
  5. A. Czumaj, M. Monemizadeh, K. Onak, and C. Sohler. Planar Graphs: Random Walks and Bipartiteness Testing. In Proceedings of the Forty-Third Annual Symposium on Foundations of Computer Science (FOCS), pages 423-432, 2011. Google Scholar
  6. A. Czumaj, A. Shapira, and C. Sohler. Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. SIAM Journal on Computing, 38(6):2499-2510, 2009. Google Scholar
  7. A. Edelman, A. Hassidim, H. N. Nguyen, and K. Onak. An Efficient Partitioning Oracle for Bounded-Treewidth Graphs. In Proceedings of the Fifteenth International Workshop on Randomization and Computation (RANDOM), pages 530-541, 2011. Google Scholar
  8. G. Elek. The combinatorial cost. ArXiv Mathematics e-prints, 2006. URL: http://arxiv.org/abs/math/0608474.
  9. G. Elek. Parameter testing with bounded degree graphs of subexponential growth. Random Structures and Algorithms, 37:248-270, 2010. Google Scholar
  10. P. Erdos and A. Renyi. Asymmetric graphs. Acta Mathematica Hungarica, 14(3):295-315, 1963. Google Scholar
  11. E. Fischer, O. Lachish, A. Matsliah, I. Newman, and O. Yahalom. On the query complexity of testing orientations for being Eulerian. ACM Transactions on Algorithms, 8(2):15:1-15:41, 2012. Google Scholar
  12. O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. Google Scholar
  13. O. Goldreich, editor. Property Testing: Current Research and Surveys. Springer, 2010. LNCS 6390. Google Scholar
  14. O. Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  15. O. Goldreich, S. Goldwasser, and D. Ron. Property Testing and its Connection to Learning and Approximation. Journal of the ACM, 45(4):653-750, 1998. Google Scholar
  16. O. Goldreich and D. Ron. A sublinear bipartite tester for bounded-degree graphs. Combinatorica, 19(3):335-373, 1999. Google Scholar
  17. O. Goldreich and D. Ron. Property Testing in Bounded Degree Graphs. Algorithmica, 32(2):302-343, 2002. Google Scholar
  18. O. Goldreich and D. Ron. On Proximity Oblivious Testing. SIAM Journal on Computing, 40(2):534-566, 2011. Google Scholar
  19. O. Goldreich and D. Ron. The Subgraph Testing Model. Electronic Colloquium on Computational Complexity (ECCC), 25:45, 2018. Google Scholar
  20. M. Gonen and D. Ron. On the Benefit of Adaptivity in Property Testing of Dense Graphs. Algorithmica, 58(4):811-830, 2010. Special issue for APPROX-RANDOM 2007. Google Scholar
  21. S. Halevy, O. Lachish, I. Newman, and D. Tsur. Testing Orientation Properties. Electronic Colloquium on Computational Complexity (ECCC), 153, 2005. Google Scholar
  22. A. Hassidim, J. Kelner, H. Nguyen, and K. Onak. Local Graph Partitions for Approximation and Testing. In Proceedings of the Fiftieth Annual Symposium on Foundations of Computer Science (FOCS), pages 22-31, 2009. Google Scholar
  23. L.S. Heath. Embedding outerplanar graphs in small books. SIAM Journal on Algebraic and Discrete Methods, 8(2):198-218, 1987. Google Scholar
  24. T. Kaufman, M. Krivelevich, and D. Ron. Tight Bounds for Testing Bipartiteness in General Graphs. SIAM Journal on Computing, 33(6):1441-1483, 2004. Google Scholar
  25. J.H. Kim, B. Sudakov, and V.H. Vu. On the asymmetry of random regular graphs and random graphs. Random Structures and Algorithms, 21(3-4):216-224, 2002. Google Scholar
  26. R. Levi and D. Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Transactions on Algorithms, 11(3):24:1-24:13, 2015. Google Scholar
  27. R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Discrete Math, 1979. Google Scholar
  28. I. Newman. Property Testing of Massively Parametrized Problems - A Survey. In O. Goldreich, editor, Property Testing - Current Research and Surveys, pages 142-157. Springer, 2010. LNCS 6390. Google Scholar
  29. I. Newman and C. Sohler. Every Property of Hyperfinite Graphs Is Testable. SIAM Journal on Computing, 42(3):1095-1112, 2013. Google Scholar
  30. M. Parnas and D. Ron. Testing the Diameter of Graphs. Random Structures and Algorithms, 20(2):165-183, 2002. Google Scholar
  31. D. Ron. Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning, 1(3):307-402, 2008. Google Scholar
  32. D. Ron. Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in Theoretical Computer Science, 5(2):73-205, 2010. Google Scholar
  33. G. Valiant. Algorithmic Approaches to Statistical Questions. PhD thesis, University of California at Berkeley, 2012. Google Scholar
  34. G. Valiant and P. Valiant. Estimating the Unseen: Improved Estimators for Entropy and Other Properties. Journal of the ACM, 64(6):37:1-37:41, 2017. 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 Imprint Privacy Contact