0
$\begingroup$

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)?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.