# How to find efficiently the independent vertex sets from a large adjacency matrix?

I have a binary adjacency matrix $$M$$ of size $$72\times 72$$. I would like to find all possible combinations of 18 non-adjacent nodes.

There are $$^{72}C_{18}$$ possible (adjacent and non-adjacenct) combinations. I want to find all valid combinations.

You can try the adjacency matrix at: How to color nodes in a adjacency graph with different colors?

If one particular node is in a valid combination, then its adjacent nodes cannot be part of that valid combination.

I am using the following code.

    all = FindIndependentVertexSet[AdjacencyGraph@M, {18, Infinity}, All];
Union @ Catenate @ Map[Subsets[#, {18}]&] @ all


The Mathematica kernel keep running........

Is it possible to find them in an efficient manner.

• @Szabolcs, can IGraph/M handle this? – dipak narayanan Dec 6 '18 at 20:01
• This is not a reasonable request. How many do you expect there to be? Have you made an estimate? Do you expect to even be able to store all of them in memory? – Szabolcs Dec 6 '18 at 20:02
• I did not see your question. Yes, IGraph/M can find cliques or independent vertex sets that are not maximal (something Mma's builtin does not do). The clique finder in particular is faster than Mathematica's, in some cases much faster. The independent vertex sets of a graph are the same as the cliques of its complement. So you can try that, for smaller graphs. – Szabolcs Dec 6 '18 at 20:13
• However, your graph may have many more of these than what is reasonable to compute. – Szabolcs Dec 6 '18 at 20:14
• @Szabolcs, can you give me the code to do this? IGIndependentVertexSets[AdjacencyGraph@M, {18}] will not do the job? – dipak narayanan Dec 6 '18 at 20:16

tl;dr This is not a reasonable thing to try to compute. The problem is too large. Try to estimate the size of the solution before you proceed.

The graph you posted in your last question was very sparse (based on a triangular grid). An empty graph on 72 nodes would have

Binomial[72, 18]
(* 41432089765583440 *)


independent vertex sets. Yours will have fewer, but not by many orders fewer.

IGraph/M has a very fast clique finder, which can be used to find independent vertex sets. Recall that the independent vertex sets of a graph are the cliques of its complement.

Let's try to do what you are asking for a smaller triangular lattice.

g = GraphComplement@IGTriangularLattice;
cl = IGCliqueSizeCounts[g, {10}]

(* {0, 0, 0, 0, 0, 0, 0, 0, 0, 126138885} *)


This will only count the cliques. It will not store them. There are $$126\,138\,885$$ independent vertex sets of size 10 in this graph of 55 vertices, considerably smaller than yours.

This would take more than

126138885*10*8/1024.^3
(* 9.39808 *)


gigabytes of memory even in the most optimistic case of having everything as packed arrays.

When I tried to retrieve these in practice, the Mathematica kernel ended up using a maximum of 38 gigabytes of memory.

Your problem is much larger. It won't be possible to store all these cliques.

• Thank you very much. But I don't get where/how have you defined the graph with 55 vertices? – dipak narayanan Dec 6 '18 at 23:30
• @dipaknarayanan I used IGTriangularLattice as an example. It has 55 vertices. – Szabolcs Dec 7 '18 at 8:51