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

Posted 2 months ago
321 Views
|
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] IndependentVertexSetQ[path,{1}]  Attachments:
2 Replies
Sort By:
Posted 2 months ago
 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/870698Note 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.