Chapter 63. Independent Sets

An independent set is a set of vertices no two of which are adjacent. Independent sets are among the most fundamental objects in graph theory. They arise naturally in scheduling, coding theory, optimization, network design, resource allocation, and computational complexity.

Independent sets represent collections of mutually compatible objects. If edges represent conflicts or incompatibilities, then an independent set selects objects without conflict.

The theory of independent sets is closely related to vertex covers, graph coloring, cliques, and optimization.

63.1 Definition

Let

$$ G=(V,E) $$

be a graph.

A subset

$$ I \subseteq V $$

is called an independent set if no two vertices in (I) are adjacent.

Equivalently,

$$ \forall u,v \in I, \quad uv \notin E. $$

Thus the subgraph induced by (I) contains no edges.

For example, in the path

$$ v_1-v_2-v_3-v_4, $$

the set

$$ {v_1,v_3} $$

is independent.

The set

$$ {v_2,v_3} $$

is not independent because

$$ v_2v_3 \in E. $$

63.2 Maximum Independent Sets

An independent set is maximum if it has largest possible size.

The size of a maximum independent set is called the independence number and is denoted by

$$ \alpha(G). $$

Thus,

$$ \alpha(G) = \max{|I| : I \text{ is an independent set}}. $$

The maximum independent set problem asks for an independent set of largest possible size.

This is one of the classical NP-complete optimization problems.

63.3 Maximal and Maximum Independent Sets

The words maximal and maximum have different meanings.

Term	Meaning
Maximal independent set	Cannot be enlarged
Maximum independent set	Largest possible size

Every maximum independent set is maximal.

The converse is false.

Example

Consider the path

$$ v_1-v_2-v_3-v_4. $$

The set

$$ {v_2,v_4} $$

is maximal.

No additional vertex can be inserted.

However,

$$ {v_1,v_3} $$

has the same size, while larger examples exist in other graphs where maximal sets are not maximum.

63.4 Independent Sets in Standard Graphs

Complete Graphs

In the complete graph

$$ K_n, $$

every pair of distinct vertices is adjacent.

Thus:

$$ \alpha(K_n)=1. $$

Empty Graphs

If a graph contains no edges, then every subset is independent.

Hence:

$$ \alpha(G)=|V|. $$

Paths

For the path graph (P_n),

$$ \alpha(P_n) = \left\lceil \frac{n}{2} \right\rceil. $$

One may choose alternating vertices.

Cycles

For the cycle graph (C_n),

$$ \alpha(C_n) = \left\lfloor \frac{n}{2} \right\rfloor. $$

Odd cycles force one conflict.

Complete Bipartite Graphs

For

$$ K_{m,n}, $$

all vertices on either side form an independent set.

Thus:

$$ \alpha(K_{m,n}) = \max(m,n). $$

63.5 Relationship with Vertex Covers

Independent sets and vertex covers are complementary notions.

Theorem 63.1

A set

$$ I \subseteq V $$

is independent if and only if

$$ V \setminus I $$

is a vertex cover.

Proof

Suppose (I) is independent.

No edge has both endpoints in (I). Therefore every edge has at least one endpoint outside (I), meaning:

$$ V \setminus I $$

covers every edge.

Conversely, suppose

$$ V \setminus I $$

is a vertex cover.

If two vertices of (I) were adjacent, the edge joining them would not be covered.

Thus (I) is independent.

This establishes the equivalence.

63.6 Independence Number and Vertex Cover Number

Because independent sets and vertex covers are complements:

$$ \alpha(G)+\tau(G)=|V|. $$

\alpha(G)+\tau(G)=|V|

This identity is fundamental in graph optimization.

It converts maximum independent set problems into minimum vertex cover problems.

63.7 Independent Sets and Cliques

A clique is a set of pairwise adjacent vertices.

Independent sets and cliques are dual under graph complementation.

Let

$$ \overline{G} $$

denote the complement graph.

Then:

$$ I \text{ is independent in } G $$

if and only if

$$ I \text{ is a clique in } \overline{G}. $$

Therefore:

$$ \alpha(G)=\omega(\overline{G}), $$

where

$$ \omega(G) $$

is the clique number.

This duality is central in extremal graph theory.

63.8 Independent Set Algorithms

Brute Force

Testing all subsets requires:

$$ 2^{|V|} $$

possibilities.

This quickly becomes infeasible.

Branch-and-Bound

More advanced exact algorithms prune large parts of the search space.

Dynamic Programming

Special graph classes admit efficient methods:

Graph Class	Complexity
Trees	Polynomial
Bipartite graphs	Polynomial via vertex cover
Interval graphs	Polynomial
General graphs	NP-complete

63.9 Independent Sets in Trees

Trees allow especially simple recursive methods.

For a vertex (v), either:

Choice	Consequence
Include (v)	Exclude all neighbors
Exclude (v)	Children remain unrestricted

Dynamic programming combines subtree solutions efficiently.

This yields linear-time algorithms on trees.

63.10 Greedy Independent Sets

A maximal independent set can be found greedily.

Algorithm

1. Choose a vertex.
2. Add it to the independent set.
3. Remove the vertex and all its neighbors.
4. Repeat.

The result is always maximal.

However, it may not be maximum.

Example

In some graphs, poor early choices lead to significantly smaller solutions.

63.11 Independent Sets and Coloring

Graph coloring partitions vertices into independent sets.

A proper coloring assigns colors so that adjacent vertices receive different colors.

Each color class is therefore independent.

If:

$$ \chi(G) $$

is the chromatic number, then:

$$ |V| \le \chi(G)\alpha(G). $$

Thus:

$$ \chi(G) \ge \frac{|V|}{\alpha(G)}. $$

Independent sets therefore provide lower bounds for coloring problems.

63.12 Weighted Independent Sets

Suppose each vertex has weight:

$$ w(v). $$

The goal becomes maximizing:

$$ \sum_{v \in I} w(v). $$

Weighted independent set problems appear in scheduling, resource allocation, and communications.

Example

If vertices represent tasks and weights represent profit, then a weighted independent set chooses mutually compatible tasks of maximum total profit.

63.13 Independent Set Polytope

Introduce variables:

$$ x_v= \begin{cases} 1, & v \in I, \ 0, & v \notin I. \end{cases} $$

The optimization becomes:

$$ \max \sum_{v \in V} x_v $$

subject to:

$$ x_u+x_v \le 1 $$

for every edge

$$ uv \in E. $$

x_u+x_v \le 1

These inequalities define the independent set polytope.

63.14 Complexity

The maximum independent set problem is NP-complete.

Moreover, it is difficult to approximate well in general graphs.

This computational difficulty makes independent sets one of the central hard problems in combinatorial optimization.

63.15 Independent Sets in Bipartite Graphs

For bipartite graphs:

$$ \alpha(G) = |V|-\tau(G). $$

Using König's theorem:

$$ \tau(G)=\nu(G), $$

so:

$$ \alpha(G) = |V|-\nu(G). $$

Thus maximum independent sets in bipartite graphs can be computed efficiently through matching algorithms.

63.16 Ramsey-Theoretic Perspective

Ramsey theory studies unavoidable structure.

Large graphs must contain either:

Structure	Meaning
Large clique	Dense organization
Large independent set	Sparse organization

Ramsey numbers quantify this phenomenon.

Independent sets therefore play a central role in extremal combinatorics.

63.17 Random Graphs

In random graphs, the independence number grows slowly relative to the number of vertices.

For the Erdős-Rényi random graph:

$$ G(n,p), $$

the independence number is typically logarithmic in (n) when (p) is fixed.

Random graph theory studies the probabilistic behavior of independent sets.

63.18 Applications

Independent sets model mutually compatible choices.

Application	Interpretation
Scheduling	Nonconflicting tasks
Wireless networks	Noninterfering transmitters
Register allocation	Simultaneously usable registers
Coding theory	Error-resistant codewords
Social networks	Mutually unrelated groups
Resource allocation	Compatible requests

The abstraction is extremely broad.

63.19 Special Graph Classes

Some graph families admit efficient independent set algorithms.

Graph Class	Status
Trees	Polynomial
Chordal graphs	Polynomial
Interval graphs	Polynomial
Perfect graphs	Polynomial
General graphs	NP-complete

Structural graph theory often studies graph classes where independent sets become tractable.

63.20 Turán-Type Questions

Extremal graph theory asks:

How many edges force small independent sets?

Turán's theorem and related results connect graph density with clique and independence structure.

Dense graphs tend to have small independent sets.

Sparse graphs tend to have larger ones.

63.21 Independent Dominating Sets

An independent dominating set is both:

Property	Meaning
Independent	No adjacent selected vertices
Dominating	Every vertex touched or selected

These sets combine sparsity with coverage.

They appear in facility placement and communication systems.

63.22 Common Relationships

Parameters	Relation
Independent set and vertex cover	(\alpha(G)+\tau(G)=
Independent set and clique	(\alpha(G)=\omega(\overline{G}))
Coloring bound	(\chi(G)\ge

These identities connect independence with multiple central graph invariants.

63.23 Exercises

1. Compute (\alpha(P_7)).

2. Compute (\alpha(C_8)).

3. Prove that every independent set complement is a vertex cover.

4. Show that:

$$ \alpha(G)+\tau(G)=|V|. $$

5. Find a maximum independent set in (K_{3,5}).

6. Explain why every color class is independent.

7. Construct a maximal independent set that is not maximum.

8. Compute the independence number of (K_6).

9. Write the linear programming formulation for maximum independent set.

10. Explain why independent set is computationally difficult in general graphs.