Testing triangle-freeness in general graphs

In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are triangle-free and reject graphs that are far from being triangle-free in the sense that a constant fraction of the edges should be removed in order to obtain a triangle-free graph. The algorithm is allowed a small probability of error. This problem has been studied quite extensively in the past, but the focus was on dense graphs, that is, when d = Θ(n), where d is the average degree in the graph and n is the number of vertices. Here we study the complexity of the problem in general graphs, that is, for varying d. In this model a testing algorithm is allowed to ask neighbor queries (i.e., “what is the i-th neighbor of vertex v”), vertex-pair queries (i.e., “is there an edge between vertices v and u”), and degree queries (i.e., “what is the degree of vertex v”). Our main finding is a lower bound of Ω(n 1/3) on the necessary number of queries that holds for every d < n 1−ν(n) , where ν(n) = o(1). Since when d = Θ(n) the number of queries sufficient for testing has been known to be independent of n, we observe an abrupt, threshold-like behavio