Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
7  
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
5  
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
2  
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
5  
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 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.