Testing the diameter of graphs

Abstract

We propose a general model for testing graph properties, which extends and simplifies the bounded degree model of Goldreich and Ron [Property Testing in Bounded Degree Graphs, Proc. 31st Annual ACM Symposium on the Theory of Computing, 1997, pp. 406-415.] In this model, we present a family of algorithms that test whether the diameter of a graph is bounded by a given parameter D, or is e-far from any graph with diameter at most β(D). The function β(D) ranges between D + 4 and 4D + 2, depending on the algorithm. All our algorithms run in time polynomial in 1/e.