This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
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.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles
This article has been given a rating which conflicts with the project-independent quality rating in the banner shell. Please resolve this conflict if possible.
This follows from the fact that if a graph has an independent set of size k, then its complement (the graph on the same vertex set, but complementary edge set) has a clique of size k.
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)[reply]
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)[reply]
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!
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)[reply]
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)[reply]
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))[reply]
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)[reply]
The article claims "Therefore, the sum of the size of the largest independent set α(G), and the size of a minimum vertex cover β(G), is equal to the number of vertices in the graph.". I think this is wrong: Consider the triangle graph K3. Any single vertex suffices to cover K3, so β(K3) = 1. Furthermore, α(K3) = 1 as well. But K3 has 3 vertices, not 2. — Preceding unsigned comment added by 84.153.28.152 (talk) 12:25, 3 August 2015 (UTC)[reply]
It's not about regularity, it's about maximum degree, it's an easy consequence of Brooks' theorem, and it has the same exceptions as Brooks' theorem (cliques and odd cycles). It might be worth mentioning, if we can find a good source. —David Eppstein (talk) 16:55, 21 April 2020 (UTC)[reply]
