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. —Preceding unsigned comment added by 203.143.165.107 (talk • contribs) 01:24, 14 August 2008

The proof is correct; no such assumption is being made. Edges are drawn between literals in the same clause so that, if an independent set of size k exists, then we know the set contains exactly one literal from each clause (because it cannot contain two literals from the same clause), so we can make those literals true (and the other literals either true or false, it doesn't matter) to get a satisfying assignment for all the literals. The independent set corresponds to a subset of the true literals in a satisfying assignment, not necessarily the entire set of true literals. —Bkell (talk) 02:37, 14 August 2008 (UTC)

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)

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)

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)

Support, but with Bkell’s suggestion of having the algorithmic aspect as a section of Independent set, rather than the other way around. Check out Graph coloring for an example. Thore Husfeldt (talk) 20:16, 12 December 2008 (UTC)

Covering-Packing Dualities

What do you think of my idea to have a box of the most prominent covering problems and their corresponding dual problems (see independent set problem)? It's definitely not complete since all pages of these problems should be augmented with the corresponding linear program formulation. And more importantly, there should be an explanation for the covering-packing duality. Still I think it helps a lot to see these problems side by side. ylloh (talk) 18:18, 11 March 2009 (UTC)