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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I've edited the title to remove the mention of persistent homology as while Vietoris-Rips complexes are frequently studied using persistent homology, your question actually doesn't touch on persistent homology at all. $\endgroup$– j.c.Commented Dec 9, 2017 at 21:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The Vietoris-Rips complex at scale $\epsilon$ of a set of points $P$ in some metric space $X$ ("data cloud") is the 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 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" by Afra Zomorodian. In particular Section 4.3 discusses the connection to clique problems.