loading...
Testing Subgraphs in Large Graphs
Las Vegas, Nevada October 14-October 17
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2001.95991842nd IEEE symposium on Foundations of ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.