Introduction

The Independent Set Problem is a fundamental graph problem that serves as an excellent example of NP-completeness. It’s closely related to the Clique Problem and Vertex Cover Problem, forming a trio of interconnected NP-complete graph problems. Understanding Independent Set provides insight into reduction techniques and the relationships between seemingly different graph problems.

What is an Independent Set?

An independent set (also called a stable set) in an undirected graph is a set of vertices where no two vertices are adjacent (connected by an edge). In other words, it’s a set of vertices with no edges between them.

Problem Definition

Independent Set Decision Problem:

Input:

  • An undirected graph G = (V, E)
  • An integer k

Output: YES if G contains an independent set of size at least k, NO otherwise

Independent Set Optimization Problem:

Input: An undirected graph G = (V, E)

Output: The size of the largest independent set in G (called the independence number, denoted alpha(G))

Example

Consider the following graph:

    1---2
    |\ /|
    | X |
    |/  |
    3---4

Edges in the graph:

  • 1-2 (top horizontal)
  • 1-3 (left diagonal )
  • 2-3 (left diagonal /)
  • 2-4 (right diagonal )
  • 3-4 (bottom horizontal)
  • Note: 1-4 is NOT connected (no edge between them)

Independent sets:

  • Independent sets of size 1: Any single vertex (e.g., {1}, {2}, {3}, {4})
  • Independent sets of size 2: {1, 4} only
    • {1, 4} is independent because vertices 1 and 4 are not connected ✓
    • {2, 3} is NOT independent because vertices 2 and 3 are connected ✗
    • All other pairs are connected
  • Independent sets of size 3: None (any three vertices will have at least one edge)
  • Maximum independent set: Size 2, which is {1, 4}

So the independence number α(G) = 2.

Visual Example

A graph with a maximum independent set highlighted:

    1---2---3
    |       |
    4---5---6
  • Independent sets: {1, 3, 5}, {2, 4, 6}, {1, 6}, {2, 5}, etc.
  • Maximum independent set: {1, 3, 5} or {2, 4, 6} (size 3)
  • Note: {1, 2} is NOT an independent set because vertices 1 and 2 are adjacent

Why Independent Set is in NP

To show that Independent Set is NP-complete, we first need to show it’s in NP.

Independent Set ∈ NP:

Given a candidate solution (a set of k vertices), we can verify in polynomial time:

  1. Check that the set has at least k vertices: O(n) time (since k ≤ n)
  2. Check that no two vertices in the set are adjacent: O(n²) time (check all pairs, and for each pair, check if an edge exists in O(1) time with an adjacency matrix or O(deg(v)) with an adjacency list)

Since k ≤ n, this verification takes polynomial time in the input size. Therefore, Independent Set is in NP.

NP-Completeness: Reduction from Clique

The most elegant proof that Independent Set is NP-complete uses the relationship between Independent Set and Clique through the complement graph.

Complement Graph

Given a graph G = (V, E), its complement graph G̅ = (V, E̅) has:

  • The same vertex set V
  • An edge (u, v) ∈ E̅ if and only if (u, v) ∉ E

In other words, G̅ has edges exactly where G doesn’t have edges.

Key Relationship

Fundamental Observation:

  • S is a clique in G if and only if S is an independent set in G̅

Proof:

  • If S is a clique in G, then every pair of vertices in S is connected by an edge in G
  • Therefore, no pair of vertices in S is connected by an edge in G̅
  • So S is an independent set in G̅
  • The reverse direction follows similarly

Reduction from Clique

Since we know Clique is NP-complete, we can reduce Clique to Independent Set:

Reduction:

  1. Given a Clique instance: graph G and integer k
  2. Construct the complement graph G̅
  3. Return Independent Set instance: graph G̅ and integer k

Correctness:

  • G has a clique of size k if and only if G̅ has an independent set of size k
  • This follows directly from the fundamental observation above

Polynomial Time:

  • Constructing G̅ takes O(n²) time (check all pairs of vertices)
  • This is polynomial in the input size

Therefore, Independent Set is NP-complete.

Alternative Reduction: Direct from 3-SAT

We can also prove Independent Set is NP-complete by directly reducing from 3-SAT, similar to the Clique reduction.

Construction

For a 3-SAT formula φ = C_1 ∧ C_2 ∧ … ∧ C_m where each clause C_i has 3 literals:

  1. Create vertices: For each literal occurrence in each clause, create a vertex
    • Label vertices as (i, j) where i is the clause number and j is the literal position
  2. Add edges: Connect two vertices (i_1, j_1) and (i_2, j_2) with an edge if:
    • They are in the same clause (i_1 = i_2), OR
    • The literals are complementary (one is the negation of the other)
  3. Set k = m: We’re looking for an independent set of size m (one vertex per clause)

Why This Works

Intuition:

  • An independent set of size m means we pick one literal from each clause
  • Since vertices in the same clause are connected, we can pick at most one per clause
  • Since complementary literals are connected, we never pick both x and ! x
  • Therefore, an independent set corresponds to a satisfying assignment

Formal Proof:

Forward Direction (3-SAT satisfiable → Independent Set exists):

  • If φ is satisfiable, there exists an assignment that makes at least one literal true in each clause
  • Pick the vertex corresponding to that true literal from each clause
  • These m vertices form an independent set because:
    • They’re from different clauses (so no edges between them by construction)
    • They can’t be complementary (both can’t be true simultaneously)

Reverse Direction (Independent Set exists → 3-SAT satisfiable):

  • If there’s an independent set of size m, we have one vertex (literal) from each clause
  • Set variables to make these literals true:
    • If literal is x_i, set x_i = TRUE
    • If literal is ! x_i, set x_i = FALSE
  • Since no complementary literals are in the independent set, this assignment is consistent
  • This assignment satisfies all clauses

Example Reduction

Consider the 3-SAT instance: φ = (x₁ ∨ x₁ ∨ x₁) ∧ (! x₁ ∨ x₁ ∨ ! x₁) ∧ (x₁ ∨ ! x₁ ∨ x₁)

Step 1: Create vertices

  • Clause 1: (1,1) for x₁, (1,2) for x₁, (1,3) for x₁
  • Clause 2: (2,1) for ! x₁, (2,2) for x₁, (2,3) for ! x₁
  • Clause 3: (3,1) for x₁, (3,2) for ! x₁, (3,3) for x₁

Step 2: Add edges

  • Connect vertices in the same clause: (1,1)-(1,2), (1,1)-(1,3), (1,2)-(1,3), etc.
  • Connect complementary literals: (1,1)-(2,1) (x₁ and ! x₁), (1,3)-(2,3) (x₁ and ! x₁), (1,2)-(3,2) (x₁ and ! x₁)

Step 3: Find independent set of size 3

  • One possible independent set: {(1,2), (2,2), (3,3)} representing x₁ from clause 1, x₁ from clause 2, and x₁ from clause 3
  • This corresponds to assignment: x₁ = TRUE (arbitrary), x₁ = TRUE, x₁ = TRUE
  • Verify: All clauses satisfied!

Relationship to Other Graph Problems

The Independent Set Problem is part of a fundamental trio of related NP-complete problems:

Clique

As we’ve seen:

  • S is a clique in G if and only if S is an independent set in G̅
  • This makes Clique and Independent Set polynomially equivalent

Vertex Cover

A vertex cover is a set of vertices C such that every edge has at least one endpoint in C.

Key Relationship:

  • S is an independent set if and only if V \setminus S is a vertex cover

Proof:

  • If S is an independent set, then no edge has both endpoints in S
  • Therefore, every edge has at least one endpoint in V \setminus S
  • So V \setminus S is a vertex cover
  • The reverse direction follows similarly

Corollary:

  • Maximum independent set size + Minimum vertex cover size = n
  • This is known as Gallai’s theorem

Maximum Matching

In bipartite graphs, there’s a connection to matching:

  • König’s theorem: In bipartite graphs, the size of the maximum matching equals the size of the minimum vertex cover
  • Combined with the independent set-vertex cover relationship, this connects independent sets to matchings in bipartite graphs

Practical Implications

Why Independent Set is Hard

The Independent Set Problem is NP-complete, which means:

  1. No Known Polynomial-Time Algorithm: Best known algorithms have exponential time complexity
  2. Brute Force: Check all 2ⁿ subsets of vertices - exponential
  3. Dynamic Programming: Can solve in O(2^n · n^2) time using inclusion-exclusion or bitmask DP
  4. Branch and Bound: Practical for small instances, but still exponential worst-case

Approximation

The Independent Set Problem has interesting approximation properties:

  • Hard to Approximate: Cannot be approximated within n^{1-\epsilon} for any \epsilon > 0 (unless P = NP)
  • Greedy Algorithm: A simple greedy algorithm achieves O(n/Delta) approximation where \Delta is the maximum degree
  • Better Approximations: For bounded-degree graphs, better approximation ratios are possible

Real-World Applications

Independent Set has numerous applications:

  1. Scheduling: Assigning non-conflicting tasks (e.g., scheduling classes, meetings)
  2. Resource Allocation: Allocating resources that cannot conflict
  3. Wireless Networks: Selecting non-interfering transmission nodes
  4. Social Networks: Finding groups of people who don’t know each other
  5. Bioinformatics: Finding non-overlapping gene sets
  6. VLSI Design: Placing components that don’t interfere

Special Cases

Some restricted versions of Independent Set are tractable:

  • Bipartite Graphs: Can be solved via maximum matching (using König’s theorem)
  • Interval Graphs: Polynomial-time algorithms exist (greedy approach works)
  • Trees: Can be solved efficiently using dynamic programming
  • Bounded Treewidth: Can be solved efficiently using tree decomposition
  • Planar Graphs: Still NP-complete, but better approximation algorithms exist

Runtime Analysis

Brute Force Approach

Algorithm: Check all C(n,k) subsets of size k

  • Time Complexity: O(C(n,k) · k^2) = O(n^k · k^2)
  • Space Complexity: O(k) for storing current subset
  • Analysis: For each subset, verify no edges exist between vertices (O(k^2) checks)

Dynamic Programming

Algorithm: Use bitmask DP similar to Clique

  • Time Complexity: O(2^n · n^2)
  • Space Complexity: O(2^n · n)
  • Subproblem: dp[mask][v] = true if there exists an independent set in vertices mask ending at v
  • Recurrence: dp[mask][v] = \bigvee_{u ∈ mask, (u,v) ∉ E} dp[mask \setminus {v}][u]

Tree DP (Special Case)

Algorithm: For trees, use bottom-up DP

  • Time Complexity: O(n)
  • Space Complexity: O(n)
  • Subproblem: dp[v][0/1] = maximum independent set in subtree rooted at v (0 = don’t include v, 1 = include v)
  • Recurrence:
    • dp[v][0] = ∑_{u ∈ children(v)} \max(dp[u][0], dp[u][1])
    • dp[v][1] = 1 + ∑_{u ∈ children(v)} dp[u][0]

Branch-and-Bound

Algorithm: Systematic search with pruning

  • Time Complexity: Exponential worst-case, improved with pruning
  • Space Complexity: O(n) for recursion stack
  • Pruning: Stop if remaining vertices can’t form independent set of size k

Verification Complexity

Given a candidate independent set of size k:

  • Time Complexity: O(n²) - check all pairs for absence of edges (since k ≤ n)
  • Space Complexity: O(1) additional space
  • This polynomial-time verifiability shows Independent Set is in NP

Key Takeaways

  1. Independent Set is NP-Complete: Proven by reduction from Clique (via complement graph) or directly from 3-SAT
  2. Complement Graph Relationship: The connection between Clique and Independent Set through complement graphs is elegant and fundamental
  3. Vertex Cover Connection: Independent Set and Vertex Cover are complementary - solving one solves the other
  4. Reduction Patterns: The 3-SAT → Independent Set reduction shows how to encode logical constraints as graph structures (opposite pattern from Clique)
  5. Practical Algorithms: Despite NP-completeness, various techniques work well for many practical instances and special graph classes

Reduction Summary

Clique ≤ₚ Independent Set:

  • Given Clique instance: graph G and integer k
  • Construct complement graph G̅
  • Return Independent Set instance: graph G̅ and integer k
  • G has clique of size k ↔ G̅ has independent set of size k

3-SAT ≤ₚ Independent Set:

  • Given 3-SAT instance with m clauses
  • Create graph with vertices for each literal occurrence
  • Connect vertices in same clause OR with complementary literals
  • 3-SAT satisfiable ↔ Graph has independent set of size m

Both reductions are polynomial-time, establishing Independent Set as NP-complete.

Further Reading

  • Garey & Johnson: “Computers and Intractability” - Standard reference for NP-completeness proofs
  • Gallai’s Theorem: The relationship between independent sets and vertex covers
  • König’s Theorem: Connection to matching in bipartite graphs
  • Approximation Algorithms: Research on approximating independent set in various graph classes

Practice Problems

  1. Prove the complement relationship: Show that S is a clique in G if and only if S is an independent set in G̅.

  2. Prove Gallai’s theorem: Show that for any graph G, \alpha(G) + \beta(G) = n where \alpha(G) is the independence number and beta(G) is the vertex cover number.

  3. Construct the graph for the 3-SAT instance: (x₁ ∨ ! x₁ ∨ x₁) ∧ (! x₁ ∨ x₁ ∨ x₁) ∧ (x₁ ∨ x₁ ∨ ! x₁) Find an independent set of size 3 and determine the corresponding satisfying assignment.

  4. Algorithm design: Design a dynamic programming algorithm to find the maximum independent set in a tree. What is its time complexity?

  5. Reduction practice: Given that Independent Set is NP-complete, show that Vertex Cover is also NP-complete using the complement relationship.

  6. Greedy algorithm: Analyze the greedy algorithm for Independent Set that repeatedly picks a vertex of minimum degree and removes it and its neighbors. What approximation ratio does it achieve?

Understanding the Independent Set Problem and its relationships to Clique and Vertex Cover provides crucial insight into the interconnected nature of NP-complete problems. The complement graph relationship is particularly elegant and demonstrates how seemingly different problems can be fundamentally related.