Testing subgraphs in large graphs

Research output: Contribution to journalConference articlepeer-review

25 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 ε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 ε 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)434-441
Number of pages8
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
DOIs
StatePublished - Jan 1 2001
Externally publishedYes
Event42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States
Duration: Oct 14 2001Oct 17 2001

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Testing subgraphs in large graphs'. Together they form a unique fingerprint.

Cite this