Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a map $\phi:M \to M$ which happens to be $K$-biLipchitz so that $\phi^2 = \phi\circ\phi$ is within $\epsilon$ of the identity. That is,

$$\frac{1}{K} d(m,n) \leq d(\phi(m),\phi(n)) \leq K d(m,n), \text{ and }$$
$$ d(\phi^2(m),m) \leq \epsilon$$ 

where the first line holds across all pairs $(m,n)$ in $M$ and the second line for all $m$ in $M$. Here are my questions:

> Is there a polynomial time (in the number of points of $M$) algorithm to check for the existence of such a $\phi$? And if so, what is it? Otherwise, are there "reasonably effective" techniques to approximate this problem?

I've tried reducing this to the Hall theorem and to linear programming but to no avail so far. It would be great if the algorithm actually produced one or more such $\phi$'s, but for now I'd just be happy with something that outperforms my idiotic brute-force approach and furnishes a yes/no answer for existence.