<p>I'm assuming you can do some preprocessing to organize your graph for this computation, since otherwise your question makes little sense.</p>

<p>In the $O(|W|d)$ algorithm, you can replace the average degree by the <a href="https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)">degeneracy</a> of $G$. For an undirected graph $G$, being $d$-degenerate means there is a vertex ordering such that each vertex has at most $d$ neighbors that are later in the ordering. To extract the induced subgraph, loop over each vertex of $W$ and test, for each of its $\le d$ later neighbors in a degeneracy ordering, whether that neighbor also belongs to $W$. Each edge is extracted once, when the loop reaches its earlier endpoint.</p>

<p>Because it tests a subset of the same pairs, this algorithm is never worse than your average degree algorithm and could in some cases be significantly better. And if you're computing worst case bounds in terms of the numbers of vertices and edges of the original graph, the average-degree algorithm can be as bad as $\Theta(|W|n)$ (if $W$ picks out vertices of unusually high degree), even for sparse graphs, while the degeneracy algorithm is always $O(|W|\sqrt m)$ (because degeneracy is always $O(\sqrt m)$).</p>

CC BY-SA 3.0
2015-12-26T16:10:29.270Z
In [this paper](http://arxiv.org/pdf/1503.07563.pdf) we prove that, based on the 3SUM conjecture, this algorithm cannot be improved by polynomial factors.
Tsvi Kopelowitz
CC BY-SA 3.0
2015-12-26T07:01:42.287Z
2015-12-26T07:01:42.287Z
David Eppstein
<p>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)$?</p>

<p>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)$.</p>

<p>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)$.</p>

<p>Can we do better than either $O(|W|^2)$ or $O(|W|d)$?</p>

<graph-algorithms>
Fast extraction of the edges of an induced subgraph
Martin Jambon
# Fast extraction of the edges of an induced subgraph

(Asked by: username_0 on 2015-12-26)

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)$?

**Tags:** graph-algorithms


---

## 1 answers

### Answer by username_1 on 2015-12-26. Score: 7 | Accepted answer

I'm assuming you can do some preprocessing to organize your graph for this computation, since otherwise your question makes little sense.

In the $O(|W|d)$ algorithm, you can replace the average degree by the [degeneracy](https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)) of $G$. For an undirected graph $G$, being $d$-degenerate means there is a vertex ordering such that each vertex has at most $d$ neighbors that are later in the ordering. To extract the induced subgraph, loop over each vertex of $W$ and test, for each of its $\le d$ later neighbors in a degeneracy ordering, whether that neighbor also belongs to $W$. Each edge is extracted once, when the loop reaches its earlier endpoint.

Because it tests a subset of the same pairs, this algorithm is never worse than your average degree algorithm and could in some cases be significantly better. And if you're computing worst case bounds in terms of the numbers of vertices and edges of the original graph, the average-degree algorithm can be as bad as $\Theta(|W|n)$ (if $W$ picks out vertices of unusually high degree), even for sparse graphs, while the degeneracy algorithm is always $O(|W|\sqrt m)$ (because degeneracy is always $O(\sqrt m)$).

> **Comments:**
> **username_2**: In [this paper](http://arxiv.org/pdf/1503.07563.pdf) we prove that, based on the 3SUM conjecture, this algorithm cannot be improved by polynomial factors.  

---

