I am working on a problem in topology which has as a subproblem the clique problem from graph theory.
The graph is undirected and reflexive, so its incidence matrix is symmetric and has 1s on the diagonal. A clique is a complete subgraph, so it is a subset of the vertices in which each pair of vertices forms an edge. For a given graph, I need all cliques, which will correspond to simplexes in the topology problem. I know that this is NP-complete, but it would be helpful to have J solutions in the cases (a) A small number of vertices. (b) A graph which may have a lot of vertices, but no large cliques. Here is my solution to part (a). I would appreciate suggestions for improvement. I have a completely different algorithm for (b). The idea is that if the number n of vertices is small, we can represent all subsets of vertices, and check individually if a given subset is a clique. I am sure that the experts can express this more concisely. bin=:[: #: [: i.&.<: [: 2&^ # f=:[: *./ # c=:(bin f^:2"1 _ ])# bin NB. Generate cliques m=:>1 1 0; 1 1 1;0 1 1 NB. example incidence matrix c m 0 0 1 0 1 0 0 1 1 1 0 0 1 1 0 I would appreciate any suggestions. Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
