= Leaf pruning for the 2-core
Use <adjacency lists> and a <FIFO queue> to implement the deletion rule in <time complexity> $O(|V|+|E|)$. Compute each initial <degree of a vertex> once, mark every <vertex> alive, and put all <vertices> of <degree of a vertex> zero or one in the <FIFO queue>. Each <vertex> is inserted at most once. Repeatedly remove the front <vertex> $v$, mark it dead, and traverse its original <adjacency list>. For each still-alive <graph neighbour> $u$, decrease the stored <degree of a vertex> of $u$ by one; if it has just become one, append $u$. A <vertex> already queued can drop from one to zero before its turn, but it stays queued and requires no second insertion. Stop when the <FIFO queue> is empty; the alive <vertices> induce $C_2(G)$.
For the displayed example, initially enqueue $(f,g,z)$ in that order. The successive <FIFO queues>, after each deletion and all its updates, are
$$
(f,g,z)\xrightarrow{-f}(g,z,e)\xrightarrow{-g}(z,e)\xrightarrow{-z}(e)\xrightarrow{-e}(d)\xrightarrow{-d}().
$$
This explains the delayed deletion of $d$: its initial <degree of a vertex> was three, but the relevant <degree of a vertex> is always its current one in the surviving <induced subgraph>. Removing only the original <vertices> of <degree of a vertex> one would give the wrong answer.
Initialization inspects every <vertex> and every <adjacency list> entry once. During deletion each original <adjacency list> is traversed at most once, so at most $2|E|$ entries are inspected in an <undirected graph>. All insertions, removals and stored-degree updates cost constant time each. Thus total <time complexity> is $O(|V|+|E|)$ and additional storage, beyond the <adjacency lists>, is $O(|V|)$. The cost includes <isolated vertices>; repeatedly rescanning the whole surviving <graph> after each deletion would lose this bound. The single-threshold <FIFO queue> method is enough for the <2-core>; the full <k-core of a graph> decomposition computes all thresholds.
Back to article page
