Message Boards Message Boards

0
|
5535 Views
|
2 Replies
|
0 Total Likes
View groups...
Share
Share this post:

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

Posted 5 years ago

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]
IndependentVertexSetQ[path,{1}]
Attachment

Attachments:
POSTED BY: Licheng Zhang
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: https://community.wolfram.com/groups/-/m/t/870698

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 BY: Szabolcs Horvát
Posted 5 years 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.

POSTED BY: Licheng Zhang
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract