期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper, we consider the question of determining whether
a function f has property P or is \e-far from any
function with property P.
The property testing algorithm is given a sample of the value
of f on instances drawn according to some distribution.
In some cases,
it is also allowed to query f on instances of its choice.
We study this question for different properties
and establish some connection to problems in learning theory
and approximation.
In particular we focus our attention on testing graph properties.
Given access to a graph G in the form of being able to query
whether an edge exists or not between a pair of vertices,
we devise algorithms to test whether the
underlying graph has properties such as being bipartite, k-colorable,
or having a -clique
(clique of density w.r.t the vertex set).
Our graph property testing algorithms are probabilistic
and make assertions which are correct
with high probability,
utilizing only a constant number of queries into the graph.
Moreover, the property testing algorithms can be used to efficiently
(i.e., in time linear in the number of vertices)
construct partitions of the graph
which correspond to the property being tested,
if it holds for the input graph.
For k-colorability this
sheds new light on the problem of approximatly coloring a k-colorable graph
