Testing subgraphs in large graphs
Author:
- 17 October 2002
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 21 (3-4) , 359-370
Abstract
LetHbe a fixed graph withhvertices, letGbe a graph onnvertices, and suppose that at least ϵn2edges have to be deleted from it to make itH‐free. It is known that in this caseGcontains at leastf(ϵ,H)nhcopies ofH.We show that the largest possible functionf(ϵ,H) is polynomial in ϵ if and only ifHis bipartite. This implies that there is a one‐sided error property tester for checkingH‐freeness, whose query complexity is polynomial in 1/ϵ,if and only if His bipartite. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 359–370, 2002Keywords
This publication has 20 references indexed in Scilit:
- Testing k-colorabilitySIAM Journal on Discrete Mathematics, 2002
- Testing MonotonicityCombinatorica, 2000
- Quick Approximation to Matrices and ApplicationsCombinatorica, 1999
- Property testing and its connection to learning and approximationJournal of the ACM, 1998
- Robust Characterizations of Polynomials with Applications to Program TestingSIAM Journal on Computing, 1996
- The Algorithmic Aspects of the Regularity LemmaJournal of Algorithms, 1994
- The core of a graphDiscrete Mathematics, 1992
- Integer sets containing no arithmetic progressionsActa Mathematica Hungarica, 1990
- Integer Sets Containing No Arithmetic ProgressionsJournal of the London Mathematical Society, 1987
- On Certain Sets of IntegersJournal of the London Mathematical Society, 1953