Given an undirected graph, I need an algorithm that outputs all the independent sets of size >= k (constant) in the graph. I know the problem is NPC, and I do not want to use the exponential brute-force solution. What I am looking for is to hear about the best solutions currently known to this problem. If someone can refer me to some known polynomial approximation algorithms that achieve good results, that would be very helpful.
2
-
1$\begingroup$ Do you mean, finds the largest independent set; counts the number of independent sets of size >= k; or outputs a list of all of them? Your question says the latter, but I don't know what you mean by an approximation algorithm (what does that even mean?). Also there's no hope for a polynomial-time algorithm if you want to output them all, as there can be exponentially many such sets. Thus, in its current form the question doesn't seem to make sense. Can you edit to clarify what you are asking? $\endgroup$– D.W. ♦Commented Mar 12, 2016 at 2:19
-
$\begingroup$ Good observation... I didn't even think of interpreting the question as an enumeration question. $\endgroup$– user340082710Commented Mar 12, 2016 at 3:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In general, the maximum independent set problem cannot be approximated to within a constant factor in polynomial time unless $P = NP$. You can do better, however, if you restrict yourself to special graph classes. For example, in interval graphs, the maximum independent set problem can be solved in polynomial time. As another example, in planar graphs, the maximum independent set problem can be approximated to within any ratio $r < 1$ in polynomial time.
There is a lot more information provided here: https://cstheory.stackexchange.com/questions/2503/maximal-classes-for-which-largest-independent-set-can-be-found-in-polynomial-tim http://www.graphclasses.org/classes/problem_Independent_set.html
If you're interested in actual implementations, the Wikipedia page has a few references: https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Software_for_searching_maximum_independent_set
answered Mar 12, 2016 at 1:12