Course contentsShow
← Computer Science
Lesson 1919 of 2,87243. Complexity TheoryFree lesson

The Independent Set Problem

Identifying a set of vertices with no edges between them and its NP-completeness.

The Independent Set Problem

You'll learn: What an independent set is in a graph and why finding one of size k is NP-complete.

What Is an Independent Set?

An independent set in a graph is a collection of vertices where no two vertices are connected by an edge. Think of it as selecting people for a team where none of the selected people know each other—if knowing someone means being connected by an edge.

For example, in a social network graph where edges represent friendships, an independent set would be a group of people with no friendships among them.

The Decision Problem

The Independent Set Problem asks: "Given a graph G and an integer k, does there exist an independent set of at least k vertices?"

This is a yes/no decision problem, perfect for complexity analysis.

Why It's in NP

If someone claims they found an independent set of size k, you can quickly verify their answer:

  1. Check that they gave you k vertices
  2. Confirm no edges exist between any pair of those vertices

This verification runs in polynomial time, placing Independent Set squarely in NP.

NP-Completeness

The Independent Set Problem is NP-complete. It can be proven by reducing from the Clique Problem (which you've already seen). The key insight: an independent set in graph G corresponds exactly to a clique in the complement graph (where you flip all edges and non-edges). Since Clique is NP-complete and we can transform it to Independent Set in polynomial time, Independent Set inherits NP-completeness.

No known polynomial-time algorithm exists for finding maximum independent sets in general graphs.

Key Takeaway: The Independent Set Problem—finding k vertices with no edges between them—is NP-complete, meaning it's both in NP (easy to verify) and as hard as any problem in NP.