Introduction to Testing Graph Properties

Webpage for a survey by Oded Goldreich


The aim of this article is to introduce the reader to the study of testing graph properties, while focusing on the main models and issues involved. No attempt is made at providing a comprehensive survey of this study, and specific results are often mentioned merely as illustrations of general themes.


  1. The General Context
  2. The Dense Graph Model
  3. The Bounded-Degree Graph Model
  4. The General Graph Model
  5. Additional Issues
Appendix: In Passing - Three Unrelated Observations: A.1 Testing Degree Regularity in the Dense Graph Model, A.2 Non-Adaptive Testers in the Bounded-Degree Graph Model, A.3 Testing Strong Connectivity with Forward Queries Only

Material available on-line

Back to either Oded Goldreich's homepage. or general list of papers.