<p>Another natural definition of $\epsilon$-close to an independent set is changing $\epsilon k^2$ edges. Unfortunataly with this definition property testing does not seem to be polynomial time solvable. The reason is that no one knows how to find a planted clique (and similarly independent set) of $o(\sqrt{n})$ vertices in a random graph of $n$ vertices faster than $n^{O(\log n)}$ time. One can show that a subgraph that is just a bit denser than average can be used to find the planted clique in polynomial time. This is evidence against there being a polynomial time algorithm for this variant of your problem for $k$ between $\log n$ and $\sqrt{n}$. </p>

<p>Reference: Feige and Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph, 1999.</p>

CC BY-SA 2.5
2010-11-17T19:24:25.893Z
2010-11-17T19:24:25.893Z
Warren Schudy
<p>This problem has indeed been studied.  Goldreich, Goldwasser and Ron studied it in <a href="http://www.eng.tau.ac.il/~danar/Public-pdf/test1.pdf">their seminal paper</a> which kicked off graph property testing, and then, Feige, Langberg, and Schechtman also have results on it in their <a href="http://portal.acm.org/citation.cfm?id=652184">FOCS '02 paper</a> "Graphs with tiny vector chromatic numbers and huge chromatic numbers".</p>

<p>Specifically, [FLS '02] show that one can distinguish between graphs with an independent set of size $\rho n$ from graphs $\epsilon$-far from being so (meaning, at least $\epsilon n^2$ edges need to be removed to create such an independent set) by choosing a random subgraph induced by $s = \tilde{O}(\rho^4/\epsilon^3)$ random vertices in the graph and checking whether the random subgraph has an independent set of size $\rho s$ or not.   ([GGR '98] showed a weaker bound on $s$ of $\tilde{O}(\rho/\epsilon^4)$.)  [FLS '02] also show a lower bound on $s$ of $\Omega(\rho^3/\epsilon^2)$.</p>

CC BY-SA 2.5
2010-11-17T19:20:22.127Z
2010-11-17T19:20:22.127Z
arnab
<p>Suppose we're given a graph $G$ and parameters $k,\epsilon$. Are there ranges of values for $k$ (or is it doable for all $k$) for which it is possible to test whether $G$ is $\epsilon$-far from having an independent set of size at least $k$ in time $O(n + \text{poly}(1/\epsilon))$ ? </p>

<p>If we use the usual notion of $\epsilon$-far (i.e at most $\epsilon n^2$ edges would need to be changed in order to obtain such a set), then the problem is trivial for $k = O(n\sqrt{\epsilon})$.  So</p>

<ul>
<li>It seems that if $k$ is larger, some sampling ideas should work to solve the problem. Is that true ? </li>
<li>Are there other notions of $\epsilon$-far (i.e maybe $\epsilon |E|$ edges instead) under which there are nontrivial results ? </li>
</ul>

<p>I'm basically looking for references at this point. </p>

<ds.algorithms><graph-theory><reference-request><property-testing>
Property Testing for Independent Sets
Suresh Venkat
# Property Testing for Independent Sets

(Asked by: username_0 on 2010-11-17)

Suppose we're given a graph $G$ and parameters $k,\epsilon$. Are there ranges of values for $k$ (or is it doable for all $k$) for which it is possible to test whether $G$ is $\epsilon$-far from having an independent set of size at least $k$ in time $O(n + \text{poly}(1/\epsilon))$ ?

If we use the usual notion of $\epsilon$-far (i.e at most $\epsilon n^2$ edges would need to be changed in order to obtain such a set), then the problem is trivial for $k = O(n\sqrt{\epsilon})$. So

* It seems that if $k$ is larger, some sampling ideas should work to solve the problem. Is that true ?
* Are there other notions of $\epsilon$-far (i.e maybe $\epsilon |E|$ edges instead) under which there are nontrivial results ?

I'm basically looking for references at this point.

**Tags:** ds.algorithms, graph-theory, reference-request, property-testing

---

## 2 answers

### Answer by username_2 on 2010-11-17. Score: 10 | Accepted answer

This problem has indeed been studied. Goldreich, Goldwasser and Ron studied it in [their seminal paper](http://www.eng.tau.ac.il/~danar/Public-pdf/test1.pdf) which kicked off graph property testing, and then, Feige, Langberg, and Schechtman also have results on it in their [FOCS '02 paper](http://portal.acm.org/citation.cfm?id=652184) "Graphs with tiny vector chromatic numbers and huge chromatic numbers".

Specifically, [FLS '02] show that one can distinguish between graphs with an independent set of size $\rho n$ from graphs $\epsilon$-far from being so (meaning, at least $\epsilon n^2$ edges need to be removed to create such an independent set) by choosing a random subgraph induced by $s = \tilde{O}(\rho^4/\epsilon^3)$ random vertices in the graph and checking whether the random subgraph has an independent set of size $\rho s$ or not. ([GGR '98] showed a weaker bound on $s$ of $\tilde{O}(\rho/\epsilon^4)$.) [FLS '02] also show a lower bound on $s$ of $\Omega(\rho^3/\epsilon^2)$.


---

### Answer by username_1 on 2010-11-17. Score: 6

Another natural definition of $\epsilon$-close to an independent set is changing $\epsilon k^2$ edges. Unfortunataly with this definition property testing does not seem to be polynomial time solvable. The reason is that no one knows how to find a planted clique (and similarly independent set) of $o(\sqrt{n})$ vertices in a random graph of $n$ vertices faster than $n^{O(\log n)}$ time. One can show that a subgraph that is just a bit denser than average can be used to find the planted clique in polynomial time. This is evidence against there being a polynomial time algorithm for this variant of your problem for $k$ between $\log n$ and $\sqrt{n}$.

Reference: Feige and Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph, 1999.


---

