Let $G = (V, E)$ be an arbitrary undirected graph and $W \subseteq V$ a subset of its vertices. What is the complexity of the best algorithms for obtaining the edges $F$ of the induced subgraph $H = (W, F)$?
We can iterate over all the pairs of vertices taken from $W$ and test whether they're in $E$ using a hash table. This has a complexity of $O(|W|^2)$.
Another algorithm is to iterate over all the neighbors of all the vertices in $W$, and keep the pairs that are in $W\times W$. If the average number of neighbors is $d$, the complexity of this algorithm is $O(|W|d)$.
Can we do better than either $O(|W|^2)$ or $O(|W|d)$?