Introduction to Testing Graph Properties
Webpage for a survey by Oded Goldreich
Abstract
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.
Contents
- The General Context
- 1.1 Why Graphs?
- 1.2 Why Testing?
- 1.3 Three Models of Testing Graph Properties;
- 1.4 Organization
- The Dense Graph Model
- 2.1 A Taste of the Known Results:
Testability in $q(\eps)$ queries,
Testability in $poly(1/\eps)$ queries,
Testability in $tildeO(1/\eps)$ queries,
Reflections;
- 2.2 Testing versus other forms of Approximation;
- 2.3 A Benchmark: Testing Bipartiteness
- The Bounded-Degree Graph Model
- 3.1 A Taste of the Known Results:
Testability in $q(\eps)$ queries,
Testability in $sqrt(N)\cdot poly(1/\eps)$ queries,
Reflections;
- 3.2 A Benchmark: Testing Bipartiteness
[A lower bound, An algorithm]
- The General Graph Model
- 4.1 A Taste of the Known Results;
- 4.2 A Benchmark: Testing Bipartiteness;
- 4.3 Reflections
- Additional Issues
- 5.1 Directed Graphs;
- 5.2 Tolerant Testing and Distance Approximation;
- 5.3 Proximity Oblivious Testing
Bibliography;
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.