View article

The standard models of testing graph properties postulate that the vertex-set consists of , where n is a natural number that is given explicitly to the tester. Here we suggest more flexible models by postulating that the tester is given access to samples the arbitrary vertex-set; that is, the vertex-set is arbitrary, and the tester is given access to a device that provides uniformly and independently distributed vertices. In addition, the tester may be (explicitly) given partial information regarding the vertex-set (e.g., an approximation of its size). The flexible models are more adequate for actual applications, and also facilitates the presentation of some theoretical results (e.g., reductions among property testing problems).