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!

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.

Regarding the algorithm, it is mentioned in the documentation:

https://igraph.org/c/html/latest/igraph-Cliques.html#igraph_independent_vertex_sets

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