# Chapter 63. Independent Sets

# 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. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29?utm_source=chatgpt.com))

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. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29?utm_source=chatgpt.com))

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)=|V|\) |
| Independent set and clique | \(\alpha(G)=\omega(\overline{G})\) |
| Coloring bound | \(\chi(G)\ge |V|/\alpha(G)\) |

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.