1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ @Szabolcs, can IGraph/M handle this? $\endgroup$
    – MGK
    Commented Dec 6, 2018 at 20:01
  • $\begingroup$ 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? $\endgroup$
    – Szabolcs
    Commented Dec 6, 2018 at 20:02
  • $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Commented Dec 6, 2018 at 20:13
  • $\begingroup$ However, your graph may have many more of these than what is reasonable to compute. $\endgroup$
    – Szabolcs
    Commented Dec 6, 2018 at 20:14
  • $\begingroup$ @Szabolcs, can you give me the code to do this? IGIndependentVertexSets[AdjacencyGraph@M, {18}] will not do the job? $\endgroup$
    – MGK
    Commented Dec 6, 2018 at 20:16

1 Answer 1

Reset to default
3
$\begingroup$

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[10];
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much. But I don't get where/how have you defined the graph with 55 vertices? $\endgroup$
    – MGK
    Commented Dec 6, 2018 at 23:30
  • $\begingroup$ @dipaknarayanan I used IGTriangularLattice[10] as an example. It has 55 vertices. $\endgroup$
    – Szabolcs
    Commented Dec 7, 2018 at 8:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.