Testing the diameter of graphs

Abstract

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 ϵ‐far from any graph with diameter at most β( D ). The function β( D ) ranges between D +4 and 4 D +2, depending on the algorithm. All our algorithms run in time polynomial in 1/ϵ. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 165–183, 2002