# 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

(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 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.)