Testing subgraphs in large graphs
Noga Alon · Random Structures and Algorithms · 2002
Abstract Let H be a fixed graph with h vertices, let G be a graph on n vertices, and suppose that at least ϵ n 2 edges have to be deleted from it to make it H ‐free. It is known that in this case G contains at least f (ϵ, H ) n h copies of H. We show that the largest possible function f (ϵ, H ) is polynomial in ϵ if and only if H is bipartite. This implies that there is a one‐sided error property tester for checking H ‐freeness, whose query complexity is polynomial in 1/ϵ, if and only if H is bipartite. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 359–370, 2002