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

Questions
1

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}]

findindepentindex.png
findindepentindex.png846×160 8.07 KB

2

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: Computationally solving "Easy Cube" and "Soma Cube" games / puzzles

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.

3

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.