<p>If the graph is uniformly sparse in the sense that every subgraph with <span class="math-container">$n$</span> vertices contains at most <span class="math-container">$d \cdot n$</span> edges for some small <span class="math-container">$d$</span>, then degeneracy ordering could be exploited to have <span class="math-container">$O(|E|)$</span> time preprocessing and <span class="math-container">$O(d \cdot |A|)$</span> time queries. In particular, one can record at most <span class="math-container">$d$</span> ``forward-edges'' for each vertex, and then check only these forward edges for adjacencies within <span class="math-container">$A$</span>.</p>
<p>On the other hand, <span class="math-container">$O(|E|)$</span> time preprocessing and <span class="math-container">$O(|A|)$</span> 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 <span class="math-container">$O(|E|)$</span> 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.)</p>

CC BY-SA 4.0
2023-09-22T06:38:53.743Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-09-23T19:14:18.183Z
@a3nm a graph contains a triangle if and only if there exists a vertex whose neighborhood is not an independent set.
Laakeri
CC BY-SA 4.0
2023-09-23T19:31:16.867Z
OK, so you do one query for the neighborhood of each vertex, total query time is $O(|E|)$. I see, thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-08-11T09:58:35.523Z
2023-08-11T09:58:35.523Z
Laakeri
<p>Suppose we have a sparse undirected graph <span class="math-container">$G = (V, E)$</span> with <span class="math-container">$|E| = O(|V|)$</span>, and we want to process it and then answer queries of the following type: given a set <span class="math-container">$A$</span>, is it an independent set in the graph.</p>
<p>The naive solution answers queries in time <span class="math-container">$O(|A|^2)$</span>, by checking each pair of vertices in <span class="math-container">$A$</span> 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.</p>

CC BY-SA 4.0
2023-08-02T12:11:17.203Z
Very good points, @Laakeri. Please consider turning them into an answer.
Vinicius dos Santos
CC BY-SA 4.0
2023-08-11T09:59:53.413Z
@ViniciusdosSantos Done.
Laakeri
<ds.algorithms><graph-theory><graph-algorithms><query-complexity><independent-set>
Independent set queries with preprocessing
Command Master
# Independent set queries with preprocessing

(Asked by: username_0 on 2023-07-21)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, query-complexity, independent-set

> **Comments:**
> **username_1**: Very good points, @username_2. Please consider turning them into an answer.  
> **username_2**: @ViniciusdosSantos Done.  

---

## 1 answers

### Answer by username_2 on 2023-08-11. Score: 4 | Accepted answer

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

> **Comments:**
> **username_3**: 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?  
> **username_2**: @a3nm a graph contains a triangle if and only if there exists a vertex whose neighborhood is not an independent set.  
> **username_3**: OK, so you do one query for the neighborhood of each vertex, total query time is $O(|E|)$. I see, thanks!  

---

