# Finding independent set of size n in an undirected graph

Is there an algorithm that, given an undirected graph, finds an independent set of size n (where n is less than or equal to the total number of vertices)?

• Definitely. Go over all possible sets of size $n$, and check whether any of them is independent. – Yuval Filmus May 31 '18 at 22:06

## 1 Answer

(Note: for the sake of standardization, I'm using $n$ for the number of vertices in the graph, and $k$ for the number you want in your independent set.)

The problem of whether such a set even exists is actually NP-complete, by reduction from the clique problem (since an independent set is a clique in the complement of the graph). So unless P=NP, you're not going to get any better than exponential time. This limits you to rather small graphs in practice.

The easiest algorithm for this is simple brute force: run through all sets of $k$ distinct vertices, and check whether each one is independent. If it is, return it. As expected for brute force, this runs in $O(n^2 2^n)$. An improvement was found by Xiao and Nagamochi in 2017, which brings this down to about $O(1.2^n)$. (Unfortunately, I don't have access to their paper, so I can't summarize their algorithm here.)