what is the algorithm for indipendent_vertex_sets?

I apologize, I could not find it in the source code for some reason.

Could the algorithm be improved with heuristics for certain classes of graphs?

Hope all is well!

If you need better performance right now, look for cliques in the complement graph.

See here: Independent set (graph theory) - Wikipedia

Regarding the algorithm, it is mentioned in the documentation:


The current implementation was ported to igraph from the Very Nauty Graph Library by Keith Briggs and uses the algorithm from the paper S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505–517, 1977.

The source code is (currently) in this file: https://github.com/igraph/igraph/blob/master/src/cliques/cliques.c

I was planning to investigate whether it makes sense to replace this algorithm with Cliquer, which we use for cliques at the moment. However, at the moment I have very little time. Any help is welcome with this. Specifically, we are interested in cases when looking for cliques in the complement graph is not better than calling igraph_independent_vertex_sets().

Things to look for:

  • Is looking for cliques in the complement ever slower than using igraph_independent_vertex_sets()?
  • Does it ever take prohibitively more memory?

The answer is likely yes, and specific examples are welcome (especially examples where clique finding is slower).

Note that igraph_cliques() and igraph_maximal_cliques() use entirely different algorithms, so the cases of all independent vertex sets vs maximal independent vertex sets should be investigated separately.

WoW!! Thank you the cliques function is incredibly fast!!! Mindblowingly fast!

Thank you, and I will see if I find any graphs in my application domain for which independent sets does better than finding the cliques!!

Wow still amazed by how good the clique code is!!!

1 Like