# Problem 99: Vertex-Distribution-Free Graph Testing

The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the “distribution-free” model of property testing (for functions) and the PAC model (for learning). In this Vertex-Distribution-Free (VDF) model of testing suggested in a recent paper [Goldreich-19a][1], one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.