Property Testing for Independent Sets

Question

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.

Answer 1

This problem has indeed been studied. Goldreich, Goldwasser and Ron studied it in their seminal paper which kicked off graph property testing, and then, Feige, Langberg, and Schechtman also have results on it in their FOCS '02 paper "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 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}$.

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