The n-clique problem

The n-clique problem, is finding all of the n sized cliques for a given graph. More generally, given a metric space and a set of elements. We can build a graph based on a distance threshold. So for a metrizable space X, a set S \subset X, and a graph G. We let nodes of G correspond to elements of S. Let d(s_n,s_m)< \epsilon \Rightarrow (v_n,v_m)\in E(G).  For some epsilon.

It should be noted that we can divide the problem into connected subgraphs if the graph is not connected, this is check-able in linear time and as such is computationally free relative to what we’re about to deal with. This also will greatly reduce the expense at lower thresholds.

There are several ways to “check” for n-cliques, though most are brute force searches and are incredibly computationally expensive.

The simplest, is to check every x\subset V(G) of n size. For a k=|S| there are k \choose n possible subsets. Which simplifies to factorial time. We also have to verify each subset: \forall v_n,v_m \in x,  (v_n,v_m)\in E(G). Which has n \choose 2 possible checks. So our total complexity is a double factorial: k!*n! …

Assuming you have all (n-1)-cliques, you can count the number of (n-1)-cliques contained in each possible n-clique, which becomes (k-1)!*k! This also requires k! memory.

We can also go by edge addition, for a subgraph of G, the addition of an edge in G will create cliques. \forall (a,b)\in V(G) added to a proto-graph H, the set of new n-cliques C_n is… C_2 = \{\{x,y\}\subset V(G) | xy \in E(G) \}\\ \forall n>2 \\C_n = \{A\cup B | a\in A\in C_{n-1}, b\in B\in C_{n-1}, |A\cap B|=n-2\}.

If we can create a hierarchy of containment for cliques this might be fairly efficient.

 

Advertisements