Talk:Maximal independent set

I added the picture from Independent set because it seems relevant and helps one understand the content a bit more. -Albinofrenchy (Not logged in)

Independent dominating sets

A thought that I do not have time to implement now: Parts of Dominating set#Independent domination could be copied or moved to this page. In general, we could emphasise more the aspect that maximal independent sets are not only independent sets but also dominating sets. Special cases such as maximal matching (and the related concept of edge dominating sets) could be better interlinked with this page. — Miym (talk) 20:52, 13 March 2009 (UTC)

Linear time algorithm

Is it worth adding to the article that a maximal independent set can be computed in linear time? --Robin (talk) 20:17, 18 December 2009 (UTC)

Sure. Also that a maximal independent set can be found efficiently in parallel [1] but not a lexicographically first maximal independent set [2]. —David Eppstein (talk) 20:31, 18 December 2009 (UTC)

Why Family of Graphs?

Certain families of graphs may, however, have much more restrictive bounds on the numbers of maximal independent sets or maximal cliques. For instance, if all graphs in a family of graphs have O(n) edges, and the family is closed under subgraphs, then all maximal cliques have constant size and there can be at most linearly many maximal cliques.[5]

What is this paragraph saying, and why does it need to be said?

If it's saying all maximal cliques in the family of graphs are the same size, I think that's wrong: the biggest (original?) graph could contain two different sized cliques.

I don't understand why it talks about a family of graphs. What is it about its conclusion that wouldn't be true if you only talked about one graph?

The link on (about?) the word "closed" in "closed under subgraphs" isn't helpful: The article on "Closure" doesn't mention graphs. I can guess what it is to be "closed under the operation of taking subgraphs", but if I have to guess, it doesn't help to be directed to an article that leaves me guessing.

Jmichael ll (talk) 04:38, 27 December 2013 (UTC)

An example: every n-vertex planar graph has at most 3n − 6 edges, a linear number. And every subgraph of a planar graph is planar. It follows from these two facts that every n-vertex planar graph has O(n) maximal cliques and that all of these cliques have size O(1) (in fact, they have size at most four). In this context, a family being "closed under subgraphs" means that if you take a subgraph of a graph in the family, you get another graph in the same family. As for "why family of graphs": a single graph can't have the property that all of its subgraphs are the same graph. —David Eppstein (talk) 05:28, 27 December 2013 (UTC)

Can you use the fact that four is the size of the maximum clique of a planar graph to prove the Four Color Theorem? Or is the Four Color Theorem where you got "four"?

Jmichael ll (talk) 03:42, 29 December 2013 (UTC)

No. There are graphs that do not have five-vertex cliques (some of them even have no triangles) which nevertheless require five colors. It is easy to prove that the five-vertex clique is not planar, but much harder to prove that all of these other five-chromatic graphs are also non-planar. —David Eppstein (talk) 04:21, 29 December 2013 (UTC)

External links modified (January 2018)

Hello fellow Wikipedians,

I have just modified 2 external links on Maximal independent set. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20070709192029/http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_749.html to http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_749.html
• Added archive https://web.archive.org/web/20070708145819/http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_750.html to http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_750.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 22:52, 22 January 2018 (UTC)

Listing all maximal independent sets

In the graph $kK_{3}$ consisting of $k={\frac {n}{3}}$ copies of the triangle graph $K_{3}$ there are exactly $3^{n/3}$ maximal independent sets. Each such set has cardinality ${\frac {n}{3}}$. So the output size for the listing all maximal independent sets problem is $\theta ({\frac {n}{3}}\cdot 3^{n/3})=\theta (n\cdot 3^{n/3})$. This means that the problem can not be solved in $\mathrm {O} (3^{n/3})=o(n\cdot 3^{n/3})$ time since just making the output takes more time. Please fix this mistake. — Preceding unsigned comment added by 85.206.130.180 (talk) 03:22, 26 April 2022 (UTC)

It can be solved in $O(3^{n/3})$ time by an algorithm that outputs the differences between successive sets rather than re-outputting every set from scratch. Also, why are you mathrming your Os and lowercasing your thetas? —David Eppstein (talk) 05:35, 26 April 2022 (UTC)