## 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.