42nd IEEE symposium on Foundations of Computer Science (FOCS?01) Testing Subgraphs in Large Graphs Las Vegas, Nevada October 14-October 17 ISBN: 0-7695-1390-5
Let H be a fixed graph with h vertices, let G be a graph on n vertices and suppose that at least \varepsilonn2 edges have to be deleted from it to make it H-free. It is known that in this case G contains at least f(\varepsilon, H)nh copies of H. We show that the largest possible function f(\varepsilon, H) is polynomial in \varepsilon 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 = \varepsilon, if and only if H is bipartite.
Citation:
N. Alon, "Testing Subgraphs in Large Graphs," focs, pp.434, 42nd IEEE symposium on Foundations of Computer Science (FOCS?01), 2001 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||