The Clique Complex is a way of constructing a simplicial complex out of a graph (https://en.wikipedia.org/wiki/Clique_complex).
Basically, it is formed by the sets of vertices in the cliques of the graph $G$.
Given that finding even one maximum clique in a graph is hard (so called NP-complete) (https://en.wikipedia.org/wiki/Clique_problem), I would expect that the complexity of constructing the clique complex should be non-polynomial? Since the construction of the Clique Complex requires finding all cliques, which surely is harder than finding the maximum clique?
However I don't find any references calculating the complexity (time complexity). Computational complexity I would suppose it is clearly NP-hard. Is there any references or estimate of the complexity? Just any rough estimate would be great.
Thanks a lot.
We certainly need exponential time (in the number of vertices) to construct the clique complex, since the clique complex has exponential size in the number of vertices (more precisely, there are $n$-vertex graphs with $3^{n/3}$ maximal cliques). And we can definitely do it in exponential time, since the trivial algorithm of "check if each set is a clique" is just $O(n^2 \cdot 2^n)$.
In practice, I don't think we mainly bother computing the clique complex in any real sense. We just think of the graph itself as being a structure which can answer queries such as "is $\sigma$ a face of $\operatorname{Cl}(G)$?" or "given a $k$-dimensional face $\sigma$, what are the $(k+1)$-dimensional faces containing it?" in polynomial time ($O(k^2)$ and $O(n)$ respectively).
Whether this is good enough or not really depends on what you want to compute. If you want the $k^{\text{th}}$ homology of $\operatorname{Cl}(G)$, for fixed $k$, then the number of relevant cliques is polynomial in $n$, and in fact the homology can be computed in polynomial time. On the other hand, if you are given any simplicial complex $L$ as input, together with the integer $k$, deciding if $H_k(L) = 0$ is already NP-hard. So it shouldn't bother us too much if figuring out $\operatorname{Cl}(G)$ is hard too. (See these slides on homology and complexity for these results and more.)