Testing subgraphs in large graphs

N. Alon

doi:10.1109/sfcs.2001.959918

Testing subgraphs in large graphs

N. Alon

Research output: Contribution to journal › Conference article › peer-review

27 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² 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 ε 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 language	English (US)
Pages (from-to)	434-441
Number of pages	8
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
DOIs	https://doi.org/10.1109/sfcs.2001.959918
State	Published - 2001
Externally published	Yes
Event	42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States Duration: Oct 14 2001 → Oct 17 2001

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Access to Document

10.1109/sfcs.2001.959918

Cite this

@article{0ce6b26e71dd4e6fb9ba76876b6d0c28,

title = "Testing subgraphs in large graphs",

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.",

author = "N. Alon",

year = "2001",

doi = "10.1109/sfcs.2001.959918",

language = "English (US)",

pages = "434--441",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "42nd Annual Symposium on Foundations of Computer Science ; Conference date: 14-10-2001 Through 17-10-2001",

}

TY - JOUR

T1 - Testing subgraphs in large graphs

AU - Alon, N.

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0035179610&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035179610&partnerID=8YFLogxK

U2 - 10.1109/sfcs.2001.959918

DO - 10.1109/sfcs.2001.959918

M3 - Conference article

AN - SCOPUS:0035179610

SN - 0272-5428

SP - 434

EP - 441

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - 42nd Annual Symposium on Foundations of Computer Science

Y2 - 14 October 2001 through 17 October 2001

ER -

Testing subgraphs in large graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this