Greedy Independent Sets and Degree Guarantees

Greedy Selection and Maximality

An independent set is a collection of vertices with no edges between them. Finding a largest such collection is an optimization problem, but a simple greedy procedure always finds an independent set that cannot be enlarged by adding another vertex. The distinction matters: being impossible to enlarge one vertex at a time does not mean the set is largest among all independent sets. Nevertheless, the graph’s maximum degree gives a guaranteed lower bound on the size of every such maximal set.

Throughout, graphs are finite and simple. For a graph \(G=(V,E)\), write \(n=|V|\), and, when \(V\) is nonempty, let \(\Delta=\Delta(G)\) be its maximum vertex degree. A set \(I\subseteq V\) is independent if no edge has both endpoints in \(I\). It is maximal if it is independent and no strictly larger independent set contains it. It is maximum if its size is at least that of every independent set. The maximum possible size is denoted by \(\alpha(G)\).

Different choices can produce different outputs. The guarantee proved below holds for every order of choices, not only for an order chosen by a special rule. We assume \(n\geq 1\), so \(\Delta\) is defined. The empty graph on no vertices has the empty independent set, but the expression involving its maximum degree is not needed here.

Proof. Each step removes at least the chosen vertex from the available set, so the algorithm terminates after at most \(n\) steps. No two chosen vertices are adjacent: after choosing \(v\), every available neighbor of \(v\) is removed and cannot be chosen later. Thus the output \(I\) is independent. At termination, every vertex outside \(I\) must have been removed as a neighbor of some chosen vertex; otherwise it would still be available. Therefore every vertex outside \(I\) is adjacent to a vertex in \(I\). Adding any outside vertex to \(I\) would create an edge within the set, so \(I\) is maximal. \(\square\)

The procedure can be implemented in polynomial time. For example, keep track of available vertices and, when a vertex is selected, scan its adjacency list to remove its available neighbors. Each vertex is selected at most once, and the scans involve at most a polynomial number of operations in \(n+|E|\). The guarantee is therefore useful as a constructive algorithmic result, not merely as an existence statement.

The Degree Bound

Each selected vertex accounts for the vertices it removes. Those groups of removed vertices are disjoint and together contain all of \(V\). If \(v\) is selected, it removes at most itself and its neighbors, hence at most \(\deg(v)+1\leq\Delta+1\) vertices. Counting all vertices by these groups gives the size bound.

Proof. Run the greedy algorithm and let its selected vertices, in order, be \(v_1,\ldots,v_k\). For each \(i\), let \(R_i\) be the vertices removed at the step when \(v_i\) is selected, including \(v_i\) itself. Every vertex is removed at exactly one step, so the sets \(R_1,\ldots,R_k\) partition \(V\). The vertices in \(R_i\) are all in the closed neighborhood of \(v_i\), consisting of \(v_i\) and its neighbors. Consequently, $$ |R_i|\leq \deg(v_i)+1\leq\Delta+1. $$ Summing over the \(k=|I|\) steps yields $$ n=\sum_{i=1}^k |R_i|\leq k(\Delta+1)=|I|(\Delta+1). $$ Since \(\Delta+1>0\), division gives \(|I|\geq n/(\Delta+1)\). The proof applies to every maximal independent set because the same counting argument can be made by assigning each vertex outside the set to one of its neighbors in the set. \(\square\)

The inequality is a real-valued lower bound: the integer size of \(I\) must therefore be at least \(\lceil n/(\Delta+1)\rceil\), where \(\lceil x\rceil\) is the least integer greater than or equal to \(x\). An equivalent count that retains more information about the selected vertices is \(n\leq\sum_{v\in I}(\deg(v)+1)\). Replacing each degree in that sum by the common upper bound \(\Delta\) gives the stated estimate.

From a Size Bound to an Approximation Guarantee

For a maximization problem, a \(\rho\)-approximation guarantee means that the algorithm’s output has value at least \(\mathrm{OPT}/\rho\), where \(\mathrm{OPT}\) is the optimum value and \(\rho\geq1\). For maximum independent set, the optimum is \(\alpha(G)\). Since \(\alpha(G)\leq n\), the degree bound immediately implies \(|I|\geq\alpha(G)/(\Delta+1)\). In fact, the same guarantee follows directly by comparing an optimum independent set with \(I\).

Proof. Let \(S\) be a maximum independent set, so \(|S|=\alpha(G)\). Maximality of \(I\) means that every vertex of \(G\), whether in \(I\) or outside it, is either in \(I\) or adjacent to a vertex of \(I\). Assign each \(x\in S\) to one such vertex \(v\in I\) with \(x=v\) or \(xv\in E\). For a fixed \(v\), at most \(\deg(v)+1\leq\Delta+1\) vertices can be assigned to it, since they must lie in its closed neighborhood. Counting the assigned vertices gives \(|S|\leq(\Delta+1)|I|\), which rearranges to the claimed inequality. \(\square\)

This is a degree-dependent guarantee: when \(\Delta\) is bounded by a fixed constant, the factor \(\Delta+1\) is constant. If the maximum degree grows with the number of vertices, the guarantee also grows; it should not then be described as a constant-factor approximation independent of the input size. The guarantee is valid without requiring a particular choice rule, but it does not say that all choices have the same output size.

Common Mistakes and When the Bound Helps

Using \(\Delta\) instead of \(\Delta+1\). Each chosen vertex accounts for itself as well as its neighbors. In the star example, replacing the denominator by \(\Delta\) would give \(n/\Delta=4/3\), incorrectly claiming that every maximal independent set has at least \(4/3\) vertices. The algorithm’s output \(\{c\}\) has size \(1\). The correct count includes the chosen vertex: its closed neighborhood has size at most \(\Delta+1\), and the correct bound is \(4/(3+1)=1\).

Confusing maximal with maximum. A maximal set cannot be enlarged by adding a single outside vertex; a maximum set has the largest size among all independent sets. In the star example, \(\{c\}\) is maximal but not maximum, since replacing the center by all three leaves gives a larger independent set. The degree guarantee does not assert that the greedy output is maximum.

The bound is useful because it needs only a maximum-degree estimate, not knowledge of an optimal independent set. It gives a predictable baseline for a simple polynomial-time algorithm. When a graph has many isolated vertices or low-degree vertices, particular greedy choices may do substantially better than the worst-case estimate; the theorem uses the common upper bound \(\Delta\), so it need not capture those finer features.