Lower bounds for testing Euclidean Minimum Spanning Trees

The Euclidean Minimum Spanning Tree problem is to decide whether a given graph G=(P,E) on a set of points in the two-dimensional plane is a minimum spanning tree with respect to the Euclidean distance. Czumaj et al. A. Czumaj, C. Sohler, M. Ziegler, Testing Euclidean Minimum Spanning Trees in the plane, Unpublished, Part II of ESA 2000 paper, downloaded from http://web.njit.edu/~czumaj/] gave a 1-sided-error non-adaptive property-tester for this task of query complexity . We show that every non-adaptive (not necessarily 1-sided-error) property-tester for this task has a query complexity of , implying that the test in A. Czumaj, C. Sohler, M. Ziegler, Testing Euclidean Minimum Spanning Trees in the plane, Unpublished, Part II of ESA 2000 paper, downloaded from http://web.njit.edu/~czumaj/] is of asymptotically optimal complexity. We further prove that every adaptive property-tester has query complexity of Ω(n1/3). Those lower bounds hold even when the input graph is promised to be a bounded degree tree.