View article

Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries). Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution (and, in addition, obtain answers to the usual graph-queries). We initiate a study of testing graph properties in such settings, while adapting the definition of distance between graphs so that it reflects the different probability weight of different vertices. Hence, the distance to the property represents the relative importance of the “part of the graph” that violates the property. We consider such “vertex-distribution free” (VDF) versions of the two most-studied models of testing graph properties (i.e., the dense graph model and the bounded-degree model).

In both cases, we show that VDF testing within complexity …