Minimum-Degree First Maximum Independent Set Algorithm

Definition

Minimum-Degree First Maximum Independent Set Algorithm

For the Maximum Independent Set problem, repeatedly select a vertex of minimum degree in the remaining induced graph, add it to the solution, and delete it together with all its remaining neighbours. Recompute degrees in the remaining graph before the next selection.
The output is a maximal independent set, but the algorithm does not guarantee half the optimum.

Algorithm and feasibility

H = G; I = empty set
while H has vertices:
    choose v of minimum degree in H
    I.add(v)
    delete v and its neighbours from H
return I

No later selected vertex is adjacent to an earlier selection, since all such neighbours were deleted. Every unselected vertex was deleted as a neighbour of a selection, so the result is maximal. Recomputing degrees by scanning the remaining graph in each iteration takes $O(n(n+m))$ time, which is polynomial.

An eleven-vertex counterexample

Minimum degree does not guarantee a half-approximation

There is an eleven-vertex graph on which every execution returns two vertices although the maximum independent set has size five.

Start with a star and a separate clique

Let $A=\{a_1,a_2,a_3,a_4\}$ be independent, join $v$ to every vertex of $A$, and let $Q=\{c_1,\dots ,c_6\}$ induce a clique. There are $1+4+6=11$ vertices.

The four neighbours of $v$ could all belong to a large independent set. We want greedy to delete them together by selecting $v$ first.

Raise every other degree without losing the five-vertex independent set

Join every vertex of $A$ to every vertex of $Q\setminus \{c_2\}$. Add no other edges.

These edges make $v$ uniquely minimum-degree, while $A\cup \{c_2\}$ remains independent. The exact degrees are
$\mathrm{deg}(v)=4,\mathrm{deg}(c_2)=5,\mathrm{deg}(a_i)=6,\mathrm{deg}(c_j)=9(j\ne 2).$

Why greedy fails

Proof

The first choice is forced

The unique minimum-degree vertex is $v$. Selecting it deletes $\{v\}\cup A$, leaving precisely the clique on $Q$.

All remaining vertices now have degree five. Whatever tie-breaking does, selecting one deletes the whole clique. The algorithm returns exactly two vertices.

Compute the optimum, not just a lower bound

The set $A\cup \{c_2\}$ is independent and has size five. Conversely, an independent set containing $v$ contains no vertex of $A$ and at most one vertex of the clique, so has size at most two. An independent set omitting $v$ has at most four vertices from $A$ and one from $Q$, so has size at most five. Hence $\alpha (G)=5$.

Compare with the claimed guarantee

The achieved ratio is $2/5<1/2$. Thus the half-approximation claim fails regardless of how ties are resolved.

The issue is not that greedy returns an invalid independent set. It returns a valid maximal set whose early selection eliminates four mutually compatible choices.