Combinatorial distance between simplicial complexes

This got too long for a comment, so I am placing it here.

I don't think there is a theory already out there, but that should not be too surprising. After all, the "combinatorial distance" between a simplicial complex and its barycentric subdivision (which, from a topological perspective, is basically the same thing) could be enormous. So, such a distance separates simplicial complexes that most topologists might consider equivalent. That being said, this sounds kind of neat so maybe we can come up with something here.

I'll denote by $|\sigma|$ the weight being assigned to each simplex $\sigma$, which in your current definition appears to be the cardinality. All simplicial complexes here will be assumed to be finite and non-empty. What should one hope for from a renovation distance $r$ between simplicial complexes?

Axiom 1: The distance $r(K,K')$ between a simplicial complex $K$ and a subcomplex $K' \subset K$ should equal $\sum_{\sigma \in K \setminus K'}|\sigma|$.

Axiom 2: Given two simplicial complexes $L$ and $K$ so that the set of subcomplexes of $K$ isomorphic to $L$ is non-empty, $r(K,L)$ should be the smallest possible $r(K,K')$ as $K'$ ranges over subcomplexes of $K$ isomorphic to $L$.

If one believes these axioms, then there are at least two constructions (dual to each other) which will produce such a distance. The basic inspiration comes from category theory: just consider the limit and the colimit of the disconnected diagram in the category of simplicial complexes with injective simplicial maps as the morphisms.

The Limit Given simplicial complexes $K$ and $L$, consider the set of all triples $(M,i,j)$ where $M$ is a simplicial complex and $i:M \to K$ and $j:M \to L$ are injective simplicial maps. To each such triple, we may assign the distance $d(M,i,j) = r(K,i(M)) + r(L,j(M))$. The smallest such $d$ achieved over all such triples does the trick. Since we have assumed non-emptiness, at least the one-vertex complex injects into both $K$ and $L$.

The Colimit Given simplicial complexes $K$ and $L$, consider the set of all triples $(M,i,j)$ where $M$ is a simplicial complex and $i:K \to M$ and $j:L \to M$ are injective simplicial maps. To each such triple, we may assign the distance $d(M,i,j) = r(M,i(K)) + r(M,j(L))$. The smallest such $d$ over all such triples does the trick. Since both $K$ and $L$ include into the disjoint union, there is at least one such triple.

Maybe the best answer is some mixture of these two. In any case, you are quite right about the complexity being high: anything one comes up with is harder than the NP-complete subgraph isomorphism problem.