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.