Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.)
