12.9
Greedy algorithm
S ← ∅
U ← V
while U is not empty:
pick any vertex v ∈ U
S ← S ∪ {v}
U ← U \ ({v} ∪ N(v)) ← remove v and its ≤ d neighbours
return S
CorrectnessAt the moment a vertex v is inserted, none of its neighbours remains in S; therefore S is an independent set. Guarantee on the size
Each iteration wipes out at most [math]d+1[/math] vertices (the chosen vertex and its neighbours). Thus, after the algorithm has processed all [math]|V|[/math] vertices, [math]|S|\ge \frac{|V|}{d+1}\,.[/math]
Because the maximum independent set has size [math]\alpha(G)\le |V|[/math], [math]|S|\;\ge\;\frac{\alpha(G)}{d+1}\,.[/math] Running time
By scanning adjacency lists once, the procedure deletes every vertex and edge at most once, giving time [math]\mathcal{O}(|V|+|E|)[/math]. Hence the greedy rule delivers an independent set at least a factor [math]1/(d+1)[/math] of optimal in linear time for graphs of maximum degree ≤ d.
Back to
Chapter 12
