Talk:Maximal independent set

Latest comment: 2 years ago by David Eppstein in topic Listing all maximal independent sets

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

edit

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)Reply

Linear time algorithm

edit

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)Reply

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)Reply

Why Family of Graphs?

edit

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)Reply

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)Reply
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)Reply
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)Reply
edit

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:

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: 5 June 2024).

  • 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)Reply

Listing all maximal independent sets

edit

In the graph   consisting of   copies of the triangle graph   there are exactly   maximal independent sets. Each such set has cardinality  . So the output size for the listing all maximal independent sets problem is  . This means that the problem can not be solved in   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)Reply

It can be solved in   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)Reply