Talk:Independent set problem

NP-hardness proof is incorrect?

It seems that the NP-hardness proof is incorrect. There seems to be an assumption that at most one literal can be true in a clause. I think whoever wrote the proof got the literals and their complements mixed up.

Other issues

"A much easier problem to solve is that of finding a maximal independent set, which is an independent set not contained in any other independent set. We begin with a single vertex. We find a vertex not adjacent to it and add it, then find a vertex adjacent to neither of these and add it, and so on until we can find no more vertices to add. At this time the set is maximal independent."

This seems to be incorrect. Consider the set a--b--c, which has three nodes (a, b, c) and two edges (a-b, b-c). According to this description, we first pick an arbitrary single vertex. For this example, we pick b. There are no non-adjacent nodes left in the set, and so we conclude that the set (b) is maximally independent. However, the set (a, c) is really maximally independent.

{b} is a maximal independent set, since it is not contained in any other independent set. It is not a maximum independent set (which is probably what you mean by "maximally independent"), but that wasn't claimed. --Mellum 22:32, 27 October 2006 (UTC)[reply]

Proposal to merge "Independent set" into this article

Twanvl has proposed (on 16 April 2008) to merge Independent set into this article. There seems to be no discussion about this proposal. I for one am opposed to such a merge. Independent sets are very important in graph theory and have many applications; the independent set problem is simply one computational problem about independent sets. I think that keeping two separate articles is best. If a merge is strongly desired, I would suggest merging Independent set problem into Independent set, not the other way around. —Bkell (talk) 05:01, 22 July 2008 (UTC)[reply]

I agree with Bkell - these two articles, while related, are clearly different and address different fields, and should not be merged (especially not the suggested direction!). There is a link from Independent set to the Independent set problem... if Twanvl feels this should be more prominently featured, ze can of course change the layout of Independent set to reflect this importance, but as Bkell says, the study of independent sets is far vaster than just this one problem, and as such I feel the current mention suffices. Mica (talk) 15:58, 22 July 2008 (UTC)[reply]