loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.