Approximate Densest Subgraph

Let $G = (V, E)$ be an undirected graph with $|V| = n$ vertices and $|E| = m$ edges.
For each $S \subset V$, denote $E(S)$ the set of edges in the subgraph induced by $S$, i.e.,

The density of the subgraph induced by $S$ is

Problem. Find $S^* \subset V$, s.t. $d_G(S^*)$ is maximized.

Greedy Algorithm

Definition. Given $S \subset V$, for each $u \in S$, define the set of edges incident to $u$ in $S$ as

$$E(u, S) \doteq \{ (u, v) \in E(S) \}.$$

Definition. A function $w: E \rightarrow V$ is called an edge assignment, if it maps each edge $(u, v) \in E$ to one of its endpoints $\{u, v \}$.

There is a linear time, 2-approximation greedy algorithm [1] which works as follows.

Greedy Algorithm.

1. $S_1 \leftarrow V$;
2. for $i \in [n]$ do
3. $\qquad$ $u_i \leftarrow \arg\min_{u \in S_i} |E(u, S_i)|$;
4. $\qquad$ $S_{i + 1} \leftarrow S_i \setminus \{ u_i \}$;
5. $\qquad$ for $e = (u_i, v) \in E(u_i, S_i)$ do
6. $\qquad$ $\qquad$ $w(e) \leftarrow u_i$;
7. $k \leftarrow \arg\max_{i \in n]} |E(u_i, S_i)|$;
8. return $S_k$;

Approximation Guarantee

Definition. Given an edge assignment $w$, for each $u \in V$, denote the set of edges assigned to $u$ as

$$A_w(u) \doteq \{ e = (u, v) \in E : w(e) = u \}.$$

The approximation guarantee relies on the following lemma.

Lemma. For edge assignment $w$ and each $S \subset V$, it holds that

$$\max_{u \in V} |A_w(u)| \ge d_G(S).$$

Proof. Observe that all edges in $E(S)$ are assigned to vertices in $S$. It follows that

$\square$

Theorem. The solution $S_k$ satisfies

$$d_G(S_k) \ge \frac{1}{2} \cdot d_G (S^*).$$

Proof.
Let $w$ be the assignment constructed by the greedy algorithm, and denote

Via the previous lemma, it holds that

Further, as $u_k$ is the vertices with minimum degree in the subgraph induced by $S_k$, $|E(u_k, S_k)|$ should be upper bounded by the average degree in $S_k$:

$\square$

Running Time

Theorem. The algorithm can be implemented in $O(m + n)$ time.

Proof.

We can maintain the degrees of the vertices in $S_i, i \in [n]$ dynamically.

1. At the beginning of the algorithm, set $d(u) = |E(u, V)| = |E(u, S_i)|$ for each $u \in V$. We maintain the invariant that $d(u) = |E(u, S_i)|$ at the beginning of each iteration $i \in [n]$.

2. At the $i^{(th)}$ iteration, when $u_i$ is removed from $S_i$ to construct $S_{i + 1}$, we decrease $d(v)$ by $1$, if $(u_i, v) \in E(S_i)$.

It is easy to see that the invariant is maintained, and the total update time is $O(m)$.

Next, we design a data structure that supports the extraction of $u_i$, the vertex with minimum degree in $S_i$, in $O(1)$ time. We keep an array with size $n$.

• Each vertex $u$ is kept in the $d(u)$-th bucket of the array. When $d(u)$ is updated, we update the bucket of $u$ correspondingly. The total update cost is $O(m)$.

• At the beginning of the algorithm, we search bucket $0, 1, \ldots$ , until we find the first non-empty bucket $j \in [n]$. Then we extract a vertex $u$ from the bucket $j$, and updates the $d(v)$ for which $v$ is neighbor of $u$ in the induced subgraph. The update decreases $d(v)$ by $1$. Therefore, the bucket $\max \{ 0, j - 1 \}$ can become non-empty at the next iteration, from which we should try to find the next vertex with minimum degree. There are $n$ iteration, and we can move backward at the array by at most $n$ steps. It follows that the total searching cost in the array is $O(n)$.

$\square$

Reference

[1] M. Charikar, “Greedy Approximation Algorithms for Finding Dense Components in a Graph,” 2000.