<p>In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from having the property. (An algorithm can be asked to succeed with 1-sided or 2-sided error.)  A graph is $\epsilon$-far from having a property if no $\epsilon \binom{n}{2}$ edges can be added/subtracted to make it have the property.</p>

<p>A property is said to be testable if it can be tested in the manner specified above in a sub-linear number of queries, or better yet, in a number of queries independent of $n$ (but not $\epsilon$).  The notion of what properties are can also be formalized, but it should be clear.</p>

<p>There are many results characterizing what properties are testable, with many examples of natural testable properties.  However, I am not aware of many <em>natural</em> properties that are known to not be testable (say in a constant number of queries) -- one that I am familiar with is testing for isomorphism to a given graph.</p>

<p>So, my question is: <strong>what natural graph properties are known <em>not</em> to be testable?</strong></p>

CC BY-SA 3.0
2012-09-25T14:00:57.347Z
(1) To clarify, are you looking for such properties in the adjacent matrix model?  In the adjacency list model (which is different from the formulation you wrote), many problems require more than a constant number of queries.  (2) You probably know this, but Goldreich, Goldwasser, and Ron (Proposition 10.2.3.2 of [JACM 1998](http://dx.doi.org/10.1145/285055.285060)) prove that there is a (not necessarily natural) graph property in NP which requires Ω(n^2) queries by using the probabilistic method.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-25T14:25:56.003Z
Thanks - adjacency matrix model is fine.  I know their result, but I'd like explicit natural properties, as opposed to the existence of some properties.
Lev Reyzin
CC BY-SA 3.0
2012-10-09T11:36:12.963Z
I'm not sure about it so I don't list it as an answer, but I think that the Shannon capacity of a graph $\Theta(G)$ is not testable. http://mathworld.wolfram.com/ShannonCapacity.html
Dimitris
<cc.complexity-theory><machine-learning><query-complexity><property-testing>
Natural, untestable graph properties
Lev Reyzin
# Natural, untestable graph properties

(Asked by: username_0 on 2012-09-25)

In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from having the property. (An algorithm can be asked to succeed with 1-sided or 2-sided error.) A graph is $\epsilon$-far from having a property if no $\epsilon \binom{n}{2}$ edges can be added/subtracted to make it have the property.

A property is said to be testable if it can be tested in the manner specified above in a sub-linear number of queries, or better yet, in a number of queries independent of $n$ (but not $\epsilon$). The notion of what properties are can also be formalized, but it should be clear.

There are many results characterizing what properties are testable, with many examples of natural testable properties. However, I am not aware of many *natural* properties that are known to not be testable (say in a constant number of queries) -- one that I am familiar with is testing for isomorphism to a given graph.

So, my question is: **what natural graph properties are known *not* to be testable?**

**Tags:** cc.complexity-theory, machine-learning, query-complexity, property-testing
> **Comments:**
> **username_1**: (1) To clarify, are you looking for such properties in the adjacent matrix model?  In the adjacency list model (which is different from the formulation you wrote), many problems require more than a constant number of queries.  (2) You probably know this, but Goldreich, Goldwasser, and Ron (Proposition 10.2.3.2 of [JACM 1998](http://dx.doi.org/10.1145/285055.285060)) prove that there is a (not necessarily natural) graph property in NP which requires Ω(n^2) queries by using the probabilistic method.  
> **username_0**: Thanks - adjacency matrix model is fine.  I know their result, but I'd like explicit natural properties, as opposed to the existence of some properties.  
> **username_2**: I'm not sure about it so I don't list it as an answer, but I think that the Shannon capacity of a graph $\Theta(G)$ is not testable. http://mathworld.wolfram.com/ShannonCapacity.html  

---

## 0 answers

