## The Subgraph Testing Model

#### Webpage for a paper by Oded Goldreich and Dana Ron

#### 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\to\{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.

#### Material available on-line

See slides for a short talk

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