Regarding algorithms to find maximal independent set in an unweighted and undirected graph: I saw many articles online that are referring to the case of which every vertex has a maximal degree of d, and then you can find an independent set of size n/(d+1) (for each such vertex, add it to the independent set and remove its neighbors from the graph).

But is there an approach on how to handle with vertices with a larger degree than d? Something about the group of neighbors of the vertex maybe?


closed as unclear what you're asking by D.W. Jul 21 '16 at 5:39

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Welcome to CS.SE! Can you ask a more specific question? What are you trying to achieve? Are you trying to find an algorithm to compute a maximal independent set? If so, what's wrong with the algorithms referenced on Wikipedia? en.wikipedia.org/wiki/Maximal_independent_set. If not, what is your question? Also, when referring to articles you've seen, it would be more useful to link to / cite a few of them, so we can see the context you're referring to. $\endgroup$ – D.W. Jul 20 '16 at 19:04
  • $\begingroup$ I'm trying to find an optimization on maximal independent set size in a graph. I know that in approximation algorithms there is a use in a liner program (or SDP) and then there is a use of some manipulation on the result to get integers. I'm trying to understand what is the approach for the listed case. @D.W. $\endgroup$ – nelson Jul 21 '16 at 5:36
  • $\begingroup$ I don't follow you at all. What do you mean by "an optimization"? Wikipedia already lists efficient algorithms for the problem of finding a MIS. What problem are you trying to solve? I don't know what you mean by "there is a use of some manipulation on the result to get integers". (Perhaps you have some context in mind you haven't told us about?) I'm afraid the question needs to be edited to make it a lot clearer what your algorithmic task is, what the context is (where did you read this?), and clarify what you are trying to achieve. $\endgroup$ – D.W. Jul 21 '16 at 5:39
  • $\begingroup$ Well I guess it will be complicated to explain myself, as my question related to approximation algorithms. I saw this article and I wanted to know what is the approach for vertices with larger degree, and if there is a bound on the size of the set in that case. @D.W. $\endgroup$ – nelson Jul 21 '16 at 8:22
  • $\begingroup$ If you want to ask a question about a paper you've been reading, at minimum, it would be extremely useful to include a full citation for the paper, a link to the paper so we can read it, and a description of the section number you're asking about (ideally with a well-selected quote to provide context). Also: are you aware that there's a difference between maximal independent set and maximum independent set? See en.wikipedia.org/wiki/Independent_set_(graph_theory). Anyway, if you'd like your question to be open here, you're going to need to edit it to clarify what's going on. $\endgroup$ – D.W. Jul 21 '16 at 17:42