Testing Subgraphs in Large Graphs

Research output: Contribution to journalArticlepeer-review

116 Scopus citations


Let H be a fixed graph with h vertices, let G be a graph on n vertices, and suppose that at least ∈n2 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)nh copies of H. We show that the largest possible function f(∈, H) is polynomial in e 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.

Original languageEnglish (US)
Pages (from-to)359-370
Number of pages12
JournalRandom Structures and Algorithms
Issue number3-4
StatePublished - 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Testing Subgraphs in Large Graphs'. Together they form a unique fingerprint.

Cite this