6
$\begingroup$

I'm trying to find all independent vertex sets for a given graph. Note that they may not be maximal independent sets.

There is a function in Mathematica called FindIndependentVertexSet. But I noticed that it actually gives the maximum sets, not just the independent ones.

In the reference there is also IndependentVertexSetQ that test vertices. BUT it does not test for maximal sets.

The first question is if such behaviour is intended. I mean that one function works for Maximal sets and the other does not.

Another question is whether I have to manually find the independent sets or there is already a built in function.

$\endgroup$
2
  • 1
    $\begingroup$ You may be interested in the "Background & Context" section of the documentation of FindIndependentVertexSet. Among other things, it states that: "Not-necessarily-maximal independent vertex sets cannot be found directly using FindIndependentVertexSet but can be simplistically enumerated by taking the union over the collection of all subsets of all maximal independent vertex sets." $\endgroup$
    – MarcoB
    Feb 16, 2016 at 22:11
  • $\begingroup$ Unfo, this is said only in online version. Or at least not in 10.3.| Thanks for this note. $\endgroup$
    – Andrew S.
    Feb 16, 2016 at 23:44

1 Answer 1

5
$\begingroup$

Here's a closely related question:

Based on Ralph Dratman's solution there, we can write (with slight modifications):

findAllCliques[g_] := 
 DeleteDuplicates[Sort /@ Join @@ Subsets /@ FindClique[g, Infinity, All]]

findAllIndependentVertexSets[g_] := findAllCliques@GraphComplement[g]

This will often be faster than the naive approach in the documentation that MarcoB mentioned.


Alternatively, the IGraph/M package has a function to find all (not just maximal) independent vertex sets.

?IGIndependentVertexSets

IGIndependentVertexSets[graphs] finds all independent vertex sets of graph.
IGIndependentVertexSets[graphs, {min, max}]
IGIndependentVertexSets[graphs, max]
IGIndependentVertexSets[graphs, {n}]

You can restrict the search to independent vertex sets between sizes min and max, or up to max, or size precisely n.

?IGMaximalIndependentVertexSets

IGMaximalIndependentVertexSets[graph] finds the maximal independent vertex sets of graph.

$\endgroup$
8
  • 1
    $\begingroup$ Disclosure: I'm the author of IGraph/M. $\endgroup$
    – Szabolcs
    Feb 16, 2016 at 22:18
  • $\begingroup$ Thanks! This works, should spend some time to understand HOW it works. Will as well check your package. However, should the in-built function work the way it does atm? As the name and description implies that it finds NOT the maximum set. Should this be reported? $\endgroup$
    – Andrew S.
    Feb 16, 2016 at 23:28
  • $\begingroup$ Edit: NVM the previous question, as MarcoB noted about this being said in Backgroung section of reference. $\endgroup$
    – Andrew S.
    Feb 16, 2016 at 23:36
  • $\begingroup$ @AndrewS. I see no point in reporting it. It is clearly by design, and the behaviour is clearly documented. They just made the function name a bit shorter by leaving out "maximal". It's the same with FindCliques. $\endgroup$
    – Szabolcs
    Feb 16, 2016 at 23:40
  • $\begingroup$ They as well added a note that Marco showed. But as I said in another comment, it's not in the 10.3 version (at least). Thanks for help! $\endgroup$
    – Andrew S.
    Feb 16, 2016 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.