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
"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.
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)
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)
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
"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.
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)
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)