CODEWITHSUNDEEP
graph-theory
i love stackoverflow
i love stackoverflow

Reputation: 1685

For a graph with n vertices, are there any polynomial time algorithms to find a k-vertex independent set?

For a graph with n vertices, how can I find a k-vertex independent set? (Actually, it doesn't have to be a polynomial-time algorithm, as long as it runs in reasonable time for n = 200, k = 10.)

Upvotes: 0

Views: 202

Answers (1)

Antimony
Antimony

Reputation: 39501

This is a NP hard problem if k isn't fixed. If k is fixed, it is trivially polynomial. Also, you're better off asking on one of the other overflow sites for pure algorithmic questions.

As for practical algorithms, what have you tried already? It's possible that even something as simple as greedy search will work with a small problem size.

Upvotes: 1

Related Questions