zbMATH — the first resource for mathematics

Three theorems regarding testing graph properties. (English) Zbl 1048.68062
Summary: Property testing is a relaxation of decision problems in which it is required to distinguish YES-instances (i.e., objects having a predetermined property) from instances that are far from any YES-instance. We presents three theorems regarding testing graph properties in the adjacency matrix representation. More specifically, these theorems relate to the project of characterizing graph properties according to the complexity of testing them (in the adjacency matrix representation). The first theorem is that there exist monotone graph properties in \(\mathcal{NP}\) for which testing is very hard (i.e., requires to examine a constant fraction of the entries in the matrix). The second theorem is that every graph property that can be tested making a number of queries that is independent of the size of the graph can be so tested by uniformly selecting a set of vertices and accepting iff the induced subgraph has some fixed graph property (which is not necessarily the same as the one being tested). The third theorem refers to the framework of graph partition problems, and is a characterization of the subclass of properties that can be tested using a one-sided error tester making a number of queries that is independent of the size of the graph.

68R10 Graph theory (including graph drawing) in computer science
05C80 Random graphs (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20 Randomized algorithms
68W25 Approximation algorithms
Full Text: DOI
[1] On properties closed under taking induced subgraphs, private communication, 2001.
[2] Alon, Combinatorica 20 pp 451– (2000)
[3] Alon, J Random Struct Alg 3 pp 289– (1992)
[4] Alon, SIAM J Discrete Math 15 pp 211– (2002)
[5] and The probabilistic method, Wiley, New York, 1992.
[6] and Sampling algorithms: Lower bounds and applications, Proc 33rd STOC, Hersonissos, Greece, 2001, pp. 266-275. · Zbl 1323.68292
[7] ?Combinatorial property testing?a survey,? Randomization methods in algorithm design (Eds., and ), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, Providence, Vol. 43, 45-59. 1998.
[8] Goldreich, J ACM 45 pp 653– (1998)
[9] and Three theorems regarding testing graph properties, TR01-010, ECCC, 2001, available from http://www.eccc.uni-trier.de/eccc/.
[10] Naor, SIAM J Comput 22 pp 838– (1993)
[11] ?Property testing (a tutorial),? Handbook on Randomized Computing (Eds., and ), Vol. II, 597-649. Kluwer Academic, Dordrecht, 2001.
[12] Rubinfeld, SIAM J Comput 25 pp 252– (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.