Talk:Independent set (graph theory)

Untitled

• 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.

Complement graph? --Abdull (talk) 13:16, 25 July 2008 (UTC)

Merger proposal

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)

I am strongly in favour of merging Independent set problem into Independent set (and, similarly, Dominating set problem into Dominating set). No, I do not think there is any need to merge Maximal independent set into Independent set; however, if we had a page Maximal independent set problem that tries to focus on algorithmic aspects and computational complexity of maximal independent sets, then I would suggest that it is merged into Maximal independent set. I just want to get rid of this "X problem" vs. "X" confusion. — Miym (talk) 20:37, 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.

1. 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.
2. 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?
3. 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)

Some comments: (2) The box of problem dualities: We already have pairs such as Vertex cover and Matching (graph theory) in the box, so this shouldn't be an issue. (3) Finding other similar pages: I checked Category:NP-complete problems + some other categories; I could only find the following pairs of pages that are similar: Clique problem vs. Clique (graph theory), Hamiltonian path problem vs. Hamiltonian path, and Dominating set problem vs. Dominating set. I have already created Talk:Dominating set#Merger proposal. — Miym (talk) 19:22, 5 December 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:

1. 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.
2. Cover algorithmic aspects that are specific to independent sets in Independent set (graph theory), and cover aspects that are common to both in Clique problem.

— Miym (talk) 17:46, 18 December 2009 (UTC)

It sounds to me, after reading the comments, that the gain, if any, is minimal and not nearly worth the effort. IMHO! Zaslav (talk) 02:59, 19 December 2009 (UTC)

I merged Independent set problem into Independent set (graph theory). I also re-used some text from Clique problem. A lot of editing is still needed... (By the way, please keep in mind that there is a separate article on maximal independent sets; any computational aspects of maximal independent sets should go there, possibly with a brief summary here). — Miym (talk) 20:21, 22 December 2009 (UTC)

NP-Hard Bias

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)

Wrong statement?

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)

Never mind, I had the definition of the vertex cover wrong. — Preceding unsigned comment added by 84.153.28.152 (talk) 12:28, 3 August 2015 (UTC)

k-regular graphs

Isn't it known that a k-regular graph on n vertices has a maximal independent set of at most ceil[n\k]?

I can't find it referenced in the article.

Darcourse (talk) 16:20, 21 April 2020 (UTC)

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)