TR07-083 Authors: Artur Czumaj, Asaf Shapira, Christian Sohler

Publication: 31st August 2007 00:26

Downloads: 1484

Keywords:

We study property testing in the model of bounded degree graphs. It

is well known that in this model many graph properties cannot be

tested with a constant number of queries and it seems reasonable to

conjecture that only few are testable with o(sqrt{n}) queries.

Therefore in this paper we focus our attention on testing graph properties for special classes of graphs, with the aim of proving the testability of general families of graph properties under the assumption that the input graph belongs to a (natural) family of graphs. We call a graph family non-expanding if every graph in this family has a weak expansion (its expansion is O(1/log^2n), where n is the graph size). A graph family is hereditary if it is closed under

vertex removal. Similarly, a graph property is hereditary if

it is closed under vertex removal. We call a graph property \Pi to

be testable for a graph family F if for every graph G \in F, in time independent of the size of G we can distinguish between the case when $G$ satisfies property \Pi and when it is far from every graph satisfying property \Pi. In this paper we prove that:

In the bounded degree graph model, any hereditary property is

testable if the input graph belongs to a hereditary and

non-expanding family of graphs.

Our result implies that, for example, any hereditary property (e.g.,

k-colorability, H-freeness, etc.) is testable in the bounded

degree graph model for planar graphs, graphs with bounded genus,

interval graphs, etc. No such results have been known before, and

prior to our work, very few graph properties have been known to be

testable for general graph classes in the bounded degree graph

model.