Problem statement

Let G be an undirected graph with $$$n$$$ vertices stored in adjacency matrix. Our goal is to find number of cliques in it (including the empty clique).

General idea

We will use the Meet-in-the-midlle (MITM) method, as described (in Russian :( $$$\,$$$) here. That approach allows to achieve a time complexity of $$$O(2^{\frac n2}n)$$$.

We can improve this by optimizing the calculation of the array $$$dp\text{_}sum[mask]$$$, which stores number of cliques in the subgraph corresponding to $$$mask$$$. By reducing the computation time from $$$O(2^{\frac n2} n$$$) as written here to $$$O(2^{\frac n2}) \,$$$ the overall complexity is reduced to $$$O(2^{\frac n2})$$$.

Calculation algorithm:

1. $$$dp\text{_}sum[0] = 1$$$
2. If the vertices defined by the mask form a clique, then $$$dp\text{_}sum[mask] = dp\text{_}sum[mask \oplus last\text{_}bit] * 2$$$, where $$$last\text{_}bit$$$ — last non-zero bit.
3. If the vertices defined by the mask do not form a clique, then there exists a pair of vertices, $$$u$$$ and $$$v$$$, that are not connected. Let $$$bit_u$$$ and $$$bit_v$$$ be the masks corresponding to $$$u$$$ and $$$v$$$ respectively. Thus, $$$dp\text{_}sum[mask] = dp\text{_}sum[mask \oplus bit_u] + dp\text{_}sum[mask \oplus bit_v] - dp\text{_}sum[mask \oplus bit_u \oplus bit_v]$$$

It is now clear that if we can find such $$$u$$$ and $$$v$$$ for each non-clique mask (where $$$u, v \in mask$$$ and there is no edge between them), the computation time of the algorithm above becomes $$$O(2^{\frac n2})$$$, .

Solution

Let's maintain an array $$$intersection[mask]$$$ which represents a mask, corresponding to the set of vertices connected to every vertex from $$$mask$$$. In such terms, the subgraph defined by mask is not a clique $$$\iff$$$ $$$mask \not \subset intersection[mask]$$$ $$$\iff$$$ $$$mask \cap (mask \oplus intersection[mask]) = diff\text{_}mask \not = 0$$$

Note that non-zero bits in $$$diff\text{_}mask$$$ correspond to vertices in the mask, that are not connected to all other vertices (from the same mask).
Let's choose on of them (e.g., the last non-zero bit in $$$diff\text{_}mask$$$) and denote it as $$$u$$$. To find the second vertex, it is sufficient to evaluate the expression $$$mask \text{&} (graph\text{_}u \oplus mask)$$$, where $$$graph\text{_}u$$$ is the "adjacency mask" of vertex $$$u$$$ (the i-th bit is non-zero $$$\iff$$$ vertices $$$u$$$ and $$$i$$$ are connected).
Then non-zero bits in the resulting expression correspond to vertices from the set that are not connected with $$$u$$$. Therefore, we can take the last non-zero bit.

Honourable mentions

1. The last non-zero bit from $$$mask$$$ can be calculated as $$$mask \, \text{&} \, (-mask)$$$
2. $$$\oplus$$$ denotes the logical XOR operation, & — logical AND operation