For me it looks like computing the Vietoris-Rips complex from a data cloud is very similar to the clique problem in graph theory, which it NP-hard.


How do the two differ and what is the computational complexity for finding the complex?



Complexity of computing the Vietoris-Rips complex
The [Vietoris-Rips complex](https://en.wikipedia.org/wiki/Vietoris%E2%80%93Rips_complex) at scale $\epsilon$ of a set of points $P$ in some metric space $X$ ("data cloud") is the [clique complex](https://en.wikipedia.org/wiki/Clique_complex) for the graph whose vertex set is $P$ and where pairs of distinct points $p\neq q$ are connected by an edge when $d\_X(p,q)\leq\epsilon$. Thus computing the Vietoris-Rips complex can be done by first computing this "$\epsilon$-neighbors" graph and then computing its clique complex.


Finding the graph of $\epsilon$-neighbors is closely related to the problem of [finding nearest neighbors](https://en.wikipedia.org/wiki/Nearest_neighbor_search) and even a brute force algorithm shows that this takes polynomial time in the number of vertices.


To compute the clique complex of any graph requires enumerating all maximal cliques. As the number of cliques in a graph can be exponentially large in the number of vertices, even giving the answer can take exponential time; thus computing the Vietoris-Rips complex can take exponential time.


For more details you can read ["Fast construction of the Vietoris-Rips complex"](https://pdfs.semanticscholar.org/e503/c24dcc7a8110a001ae653913ccd064c1044b.pdf) by Afra Zomorodian. In particular Section 4.3 discusses the connection to clique problems.


