# Property Testing for Independent Sets

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.

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)$.
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}$.