Article

A Characterization of the (natural) Graph Properties Testable with One-Sided Error

Authors:

Asaf ShapiraAuthors Info & Claims

FOCS '05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science

Pages 429 - 438

https://doi.org/10.1109/SFCS.2005.5

Published: 23 October 2005 Publication History

Abstract

The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property-testing. Our main result in this paper is a solution of an important special case of this general problem; Call a property tester oblivious if its decisions are independent of the size of the input graph. We show that a graph property P has an oblivious one-sided error tester, if and only if P is (semi) hereditary. We stress that any "natural" property that can be tested (either with one-sided or with two-sided error) can be tested by an oblivious tester. In particular, all the testers studied thus far in the literature were oblivious. Our main result can thus be considered as a precise characterization of the "natural" graph properties, which are testable with one-sided error. One of the main technical contributions of this paper is in showing that any hereditary graph property can be tested with one-sided error. This general result contains as a special case all the previous results about testing graph properties with one-sided error. These include the results of [17] and [5] about testing k-colorability, the characterization of [18] of the graph-partition problems that are testable with 1-sided error, the induced vertex colorability properties of [3], the induced edge colorability properties of [13], a transformation from 2-sided to 1-sided error testing [18], as well as a recent result about testing monotone graph properties [10]. More importantly, as a special case of our main result, we infer that some of the most well studied graph properties, both in graph theory and computer science, are testable with one-sided error. Some of these properties are the well known graph properties of being Perfect, Chordal, Interval, Comparability and more. None of these properties was previously known to be testable.

References

[1]

N. Alon, Testing subgraphs in large graphs, Random Structures and Algorithms 21 (2002), 359-370.

[2]

N. Alon, R. A. Duke, H. Lefmann, V. Rödl and R. Yuster, The algorithmic aspects of the Regularity Lemma, J. of Algorithms 16 (1994), 80-109.

[3]

N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451-476.

[4]

N. Alon, M. Krivelevich, I. Newman and M. Szegedy, Regular languages are testable with a constant number of queries, SICOMP 30 (2001), 1842-1862.

[5]

N. Alon and M. Krivelevich, Testing k-colorability, SIAM J. Discrete Math., 15 (2002), 211-227.

[6]

N. Alon and A. Shapira, A characterization of easily testable induced subgraphs, SODA 2004, 935-944.

[7]

N. Alon and A. Shapira, Testing satisfiability, Journal of Algorithms, 47 (2003), 87-103.

[8]

N. Alon and A. Shapira, Testing subgraphs in direcled graphs, JCSS 69/3 (2004), 354-382.

[9]

N. Alon and A. Shapira, A separation theorem in property-testing, manuscript.

[10]

N. Alon and A. Shapira, Every monotone graph-property is testable, Proc. of STOC 2005, 128-137.

[11]

M. Blum, M. Luby and R. Rubinfeld, Self-testing/correcting with applications to numerical problems, JCSS 47 (1993), 549-595.

[12]

T. M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms 46 (2003), 178-189.

[13]

E. Fischer, Testing graphs for colorability properties, Proc. of the 12th SODA (2001), 873-882.

[14]

E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science 75 (2001), 97-126.

[15]

E. Fischer and I. Newman, Testing versus estimation of graph properties, Proc. of STOC 2005, 138-146.

[16]

E. Fischer, I. Newman and J. Sgall, Functions that have readtwice constant width branching programs are not necessarily testable, Random Structures and Algorithms, in press.

[17]

O. Goldreich, S. Goldwasser and D. Ron, Property testing and its connection to learning and approximation, JACM 45(4): 653-750 (1998).

[18]

O. Goldreich and L. Trevisan, Three theorems regarding testing graph properties, FOCS 2001, 460-469.

[19]

M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.

[20]

T. A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, SIAM, Philadelphia, PA, 1999.

[21]

I. Newman, Testing of functions that have small width branching programs, FOCS 2000, 251-258.

[22]

J. L. Ramírez-Alfonsín (Editor), B. A. Reed (Editor), Perfect Graphs, Wiley, 2001.

[23]

V. Rödl and R. Duke, On graphs with small subgraphs of large chromatic number, Graphs and Comb. 1 (1985), 91-96.

[24]

D. Ron, Property testing, in: P. M. Pardalos, S. Rajasekaran, J. Reif and J. D. P. Rolim, editors, Handbook of Randomized Computing , Vol. II, Kluwer Academic Publ., 2001, 597-649.

[25]

R. Rubinfeld and M. Sudan, Robust characterization of polynomials with applications to program testing, SIAM J. on Computing 25 (1996), 252-271.

[26]

E. Szemerédi, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau, eds.), 1978, 399-401.

Cited By

Kawarabayashi KYoshida YBoneh DRoughgarden TFeigenbaum J(2013)Testing subdivision-freenessProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488663(437-446)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488663
Hoppen CKohayakawa YSampaio R(2012)A note on permutation regularityDiscrete Applied Mathematics10.1016/j.dam.2011.06.002160:18(2716-2727)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1016/j.dam.2011.06.002
Goldreich O(2011)Introduction to testing graph propertiesStudies in complexity and cryptography10.5555/2028116.2028150(470-506)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2028116.2028150
Show More Cited By

Index Terms

A Characterization of the (natural) Graph Properties Testable with One-Sided Error
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
  2. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields

Recommendations

A Characterization of the (Natural) Graph Properties Testable with One-Sided Error

The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property testing. Our main result in this paper is a solution of an important special case of this general problem:...
A combinatorial characterization of the testable graph properties: it's all about regularity
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

A common thread in recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given ...
On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
Abstract
We study property testing of (di)graph properties in bounded-degree graph models. The study of graph properties in bounded-degree models is one of the focal directions of research in property testing in the last 15 years. However, despite the many ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

FOCS '05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science

October 2005

645 pages

ISBN:0769524680

Publisher

IEEE Computer Society

United States

Publication History

Published: 23 October 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kawarabayashi KYoshida YBoneh DRoughgarden TFeigenbaum J(2013)Testing subdivision-freenessProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488663(437-446)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488663
Hoppen CKohayakawa YSampaio R(2012)A note on permutation regularityDiscrete Applied Mathematics10.1016/j.dam.2011.06.002160:18(2716-2727)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1016/j.dam.2011.06.002
Goldreich O(2011)Introduction to testing graph propertiesStudies in complexity and cryptography10.5555/2028116.2028150(470-506)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2028116.2028150
Goldreich O(2010)Introduction to testing graph propertiesProperty testing10.5555/1986603.1986612(105-141)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1986603.1986612
Goldreich O(2010)Introduction to testing graph propertiesProperty testing10.5555/1980617.1980626(105-141)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1980617.1980626
Bhattacharyya AXie NCharikar M(2010)Lower bounds for testing triangle-freeness in Boolean functionsProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873610(87-98)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873610
Hoppen CKohayakawa YMoreira CSampaio RCharikar M(2010)Property testing and parameter testing for permutationsProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873608(66-75)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873608
Elek G(2010)Parameter testing in bounded degree graphs of subexponential growthRandom Structures & Algorithms10.5555/1841364.184136737:2(248-270)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.5555/1841364.1841367
Jordan CZeugmann T(2009)Relational properties expressible with one universal quantifier are testableProceedings of the 5th international conference on Stochastic algorithms: foundations and applications10.5555/1814087.1814103(141-155)Online publication date: 26-Oct-2009
https://dl.acm.org/doi/10.5555/1814087.1814103
Alon NStav U(2009)Hardness of edge-modification problemsTheoretical Computer Science10.1016/j.tcs.2009.07.002410:47-49(4920-4927)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.07.002
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents