# Independent set queries with preprocessing

Suppose we have a sparse undirected graph $$G = (V, E)$$ with $$|E| = O(|V|)$$, and we want to process it and then answer queries of the following type: given a set $$A$$, is it an independent set in the graph.

The naive solution answers queries in time $$O(|A|^2)$$, by checking each pair of vertices in $$A$$ and making sure it isn't an edge. Are there faster algorithms? Was there any research done on this problem? I couldn't find anything.

• Very good points, @Laakeri. Please consider turning them into an answer. Aug 2, 2023 at 12:11
• @ViniciusdosSantos Done. Aug 11, 2023 at 9:59

If the graph is uniformly sparse in the sense that every subgraph with $$n$$ vertices contains at most $$d \cdot n$$ edges for some small $$d$$, then degeneracy ordering could be exploited to have $$O(|E|)$$ time preprocessing and $$O(d \cdot |A|)$$ time queries. In particular, one can record at most $$d$$ forward-edges'' for each vertex, and then check only these forward edges for adjacencies within $$A$$.
On the other hand, $$O(|E|)$$ time preprocessing and $$O(|A|)$$ time queries in the general case seem unlikely: If we would have such an algorithm, then we could check if the graph contains a triangle in $$O(|E|)$$ time. This would be a breakthrough result, and could violate some assumptions in fine-grained complexity. (I'm not really an expert in this, you should try to search for assumptions related to triangle finding.)
• OK, so you do one query for the neighborhood of each vertex, total query time is $O(|E|)$. I see, thanks!