This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Some time ago it was suggested to merge this page into Independent set problem. Nobody seems to want that, (see Talk:Independent set problem. But the other direction makes a lot of sense, at least to me. The idea is to have a page for Independent set where the algorithmic aspects form a section. Currently, Independent set and Independent set problem contain a lot of overlapping information. I think it’s a no-brainer, but there was some opposition at least to the old proposal (which I also opposed), and I’m not sure if there are editors who oppose to any kind of merge, no matter which direction. Thore Husfeldt (talk) 20:53, 14 December 2008 (UTC)
I don't think such a merge is necessary, but I don't necessarily oppose it. I think Independent set should focus on the definition, some basic facts, and interpretations of independent sets, while Independent set problem should focus on that particular algorithmic problem. Overlap in the two articles should be addressed by referring to the other article as appropriate. On the other hand, like I said, I'm not flat-out opposed to such a merge. —Bkell (talk) 00:02, 15 December 2008 (UTC)
With a similar logic, would you want to merge maximal independent set into independent set, too? (see only the vast amount of references there, it might deserve its own article). I weakly vote for a merge since the way it is currently is very confusing. ylloh (talk) 17:58, 13 March 2009 (UTC)
It would make sense to have a section of "X" devoted to "X problem", but after viewing Independent set problem I see a few weak reasons not to.
The "problem" page is much longer than the Independent set page. A merger would unbalance the content in favor of algorithmics over theory. I don't think that's representative of the subject.
There's a nice box of "problem" dualities. In a merger, this ought to be changed to a box of "structure" dualities, i.e., set covering vs. set packing instead of set covering problem vs. set packing problem. In fact, that probably ought to be done anyway. But it's extra work. Who would want to do that work, for not much return?
In line with the previous reason, it doesn't make sense to merge only one pair of pages, but all pairs of a similar nature would have to be hunted down and merged. That's a lot of extra work!
So, I don't oppose merging but I doubt it's worth the effort. Zaslav (talk) 03:15, 20 September 2009 (UTC)
I also agree with the merge. For instance, graph coloring gives a nice example of how a graph theory topic and its related algorithmic problem are treated well in the same article. --Robin (talk) 02:16, 2 November 2009 (UTC)
A merger proposal of a different kind is of course to merge this page inte Clique problem. There is almost nothing to be said about algorithms for independent set that is not also true for clique, and vice versa, so I don’t see these two topics as being sufficiently separate. Thore Husfeldt (talk) 15:57, 18 December 2009 (UTC)
I think you mean merging Independent set problem into Clique problem? One of the issues is that almost nothing isn't nothing. Where would we cover the algorithmic issues related to independent sets (but not cliques)? Some possibilities:
Rename the target page. Something like Finding cliques and independent sets might be reasonable? Then it'd make sense to have subsections that discuss issues related to independent sets.
Is there a reason that a polynomial-time solution to the Independent Set problem is repeatedly called unlikely? P = NP has neither been proven nor disproven. Thus it cannot be legitimate to say it's unlikely that P = NP because no one has proven it yet, because by that reasoning it could be said that it is in fact likely that P = NP because there is a correlation and no one has disproven it. Considering there is no probability model for how likely NP = P is to be true, calling it likely or not seems unscientific at best and very possibly personally biased with regard to NP-completeness. (Trench8891 (talk) 15:39, 14 December 2010 (UTC))
Indeed such a phrasing isn't meant in a technically formal way. However, many authors use the term 'unlikely' in that context. And it's not unscientific to do this as the precise meaning is very clear from the context. ylloh (talk) 13:10, 15 December 2010 (UTC)