Labeling vertices in a graph

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.

-
The magic words are "isoperimetric embedding into hypercubes". The general problem is NP-complete. – Ben Barber Nov 27 '13 at 15:46
That should of course be "isometric". – Ben Barber Nov 27 '13 at 16:06
arxiv.org/pdf/0705.1025.pdf This claims that it is polynomial. I hope this proves that P=NP :-P – Nathann Cohen Nov 27 '13 at 16:51
It is NP-complete is $k$ is fixed citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.93.6740 , and polynomial if you allow yourself arbitrary $k$, with the aforementionned algorithm by David Eppstein. – Arnaud Nov 27 '13 at 17:36
It is polynomial, and when it exists the labeling is unique (up to permutation and flipping of the bits of the labels and insertion/deletion of bits that are the same for all vertices). So solving it for fixed $k$ is not any harder: just find the labeling and then test whether it uses $k$ or fewer bits. The NP-complete problem is a different one where you have to preserve adjacency but not nonadjacency nor distances. – David Eppstein Nov 28 '13 at 5:09

1 Answer

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)$.

-