Property Testing in Massive Graphs

Oded Goldreich

We consider the task of evaluating properties of graphs that are too big to be even scanned. Thus, the input graph is given in form of an oracle which answers questions of the form  is there an edge between vertices u and v, or who is the i^th neighbor of v. Our task is to determine whether a given input graph has a predetermined property or is "relatively far" from any graph having the property. Distance between graphs is measured as the fraction of the possible queries on which the corresponding oracles, representing the two graphs, differ. We show that randomized algorithms of running-time substantially smaller than the size of the input graph may reach (with high probability) a correct verdict regarding whether the graph has some predetermined property (such as being bipartite) or is far from having it.

Keywords: Bipartite graphs, Property testing, Randomized algorithms.