Message Boards Message Boards


Get right result with FindIndependentVertexSet[g,{n}] ?

Posted 1 month ago
2 Replies
0 Total Likes

Hi! I konw the function FindIndependentVertexSet[g, {n}l] which finds an independent vertex set with exactly n vertices. We konw 4- Path graph, every single vertex is its 1- indepent vertex set . but we use the function FindIndependentVertexSet[g, {1}l],it returns empty set {}. It may return {{1},{2},{3},{4}}. The following text give out all of the original code proceedings. it is strange,How to solve it.

path4 = Graph[{{1, 2}, {2, 3}, {3, 4}}, VertexLabels -> All]
FindIndependentVertexSet[path4, {1}, All]

2 Replies

This is because both FindIndependentVertexSet and FindClique finds a maximal set.

While {1} is an independent vertex set, it is not maximal: it is a subset of {1,3}.

My IGraph/M package provides functions to find either all independent sets / cliques, or maximal ones.

Find those of size 1:

In[210]:= IGIndependentVertexSets[path4, {1}]
Out[210]= {{1}, {2}, {3}, {4}}

Find all:

In[212]:= IGIndependentVertexSets[path4]
Out[212]= {{1}, {2}, {3}, {4}, {1, 3}, {1, 4}, {2, 4}}

However, at this point, these functions lack the ability to find only a limited number of such sets. They will always find all of them. If you need this ability, please let me know and I will consider it for future versions (no promises, but things requested by users will get higher priority).

Other relevant functions in IGraph/M are IGMaximalIndependentVertexSets, IGCliques, IGMaximalCliques, IGLargestCliques, IGCliqueSizeCounts, and quite a few others. In particular IGCliques and related functions are far faster than Mathematica's built-ins. You will find a cool application here:

Note that I have not yet transitioned all the independent vertex set functions to the new fast algorithms, so sometimes finding cliques in the complement graph may be faster than finding independent sets in the graph.

Posted 1 month ago

Thank you very much for your help, Before you introduce your IGraph function, If I want to get k- IndependentVertexSets, I can only find all the vertices subset of order k and using function IndependentVertexSetQ. It is not convient convenient.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract