A characterization of the (natural) graph properties testable with one-sided error

Noga Alon, Asaf Shapira

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Pages429-438
Number of pages10
DOIs
StatePublished - Dec 1 2005
Externally publishedYes
Event46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States
Duration: Oct 23 2005Oct 25 2005

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2005
ISSN (Print)0272-5428

Other

Other46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
CountryUnited States
CityPittsburgh, PA
Period10/23/0510/25/05

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'A characterization of the (natural) graph properties testable with one-sided error'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., & Shapira, A. (2005). A characterization of the (natural) graph properties testable with one-sided error. In Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 (pp. 429-438). [1530735] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2005). https://doi.org/10.1109/SFCS.2005.5