Testing Subgraphs in Large Graphs

Research output: Contribution to journalArticlepeer-review

84 Scopus citations

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 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
Volume21
Issue number3-4
DOIs
StatePublished - Jan 1 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

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

Cite this