Is there an efficient algorithm for the following task?:
Given a graph $G$, either find a labelling of vertices with bit strings of length $k$ such that the labels of adjacent vertices differ in exactly one bit, and that for every pair of vertices $(u,v)$ the distance from $u$ to $v$ is the same as the number of positions in which the labels of $u$ and $v$ differ, or decide that no such labelling exists.
As the comments have already indicated, there is an $O(n^2)$ algorithm for finding such labelings without the restriction on $k$: see arXiv:0705.1025. And the labeling, if it exists, is essentially unique, so once you have computed it you can easily test if it uses $k$ or fewer bits.
But reinterpreting your question as asking whether there's a more efficient algorithm when $k$ is a small parameter (it can't be constant, but it could be as small as logarithmic): the answer is yes and no. You can find each bit of a valid labeling (when a labeling exists) by a breadth first search (see the same paper), so you can find the whole labeling in time $O(k(n+m))$ where $n$ and $m$ are the number of vertices and edges in the input. And I'm pretty sure the same bit-parallel technique for doing multiple BFS's at once that I used in the paper will work again in this case and reduce the time to $O(kn+m)$. That may be significantly less than $n^2$, especially because $m$ is always $O(n\log n)$ in graphs that can be labeled in this way. But, I don't know of a way to test whether the result is actually a valid labeling, any faster than $O(n^2)$.
