4
$\begingroup$

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.

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

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Sorry, I'm not sure I see the argument in the second paragraph -- how can you use the independent set structure to check if the graph contains a triangle? $\endgroup$
    – a3nm
    Sep 22, 2023 at 6:38
  • $\begingroup$ @a3nm a graph contains a triangle if and only if there exists a vertex whose neighborhood is not an independent set. $\endgroup$
    – Laakeri
    Sep 23, 2023 at 19:14
  • $\begingroup$ OK, so you do one query for the neighborhood of each vertex, total query time is $O(|E|)$. I see, thanks! $\endgroup$
    – a3nm
    Sep 23, 2023 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.