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:
- Check that they gave you k vertices
- 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.