MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community
Dears
Let $G$ be a graph with $n$ vertices and let $T(G)$ be the set of all bijections from vertices $V(G)$ of $G$ to the set $\{1,\dots,n\}$. Let $E(G)$ be as ususal the set of edges of $G$. Is the following problem well-known? Has it a well-accepted name in the litratures? Do you know of any result about it?
Compute $$\min_{\sigma \in T(G)} \max_{vw \in E(G)} |\sigma(v)-\sigma(w)|$$
I was thinking, that has a name, that has a name, and mathoverflow knew it, it was on the related column on the right. The invariant is often called the bandwidth of a graph. As Professor Rivin already mentioned it is NP-complete to compute it. There is however a pretty $(log n)^c$-approximation algorithm by Fiege, he generalizes Bourgain's embedding theorem and the London-Linial-Rabonovich approximation of the sparsets cut, by first generalizing bilipschitz distortion to something he calls "volume preserving embeddings". It is informally explained in chapter 15 of Matousek's "Lectures on Discrete Geometry", that is available online.
For a very similar problem, see http://www2.research.att.com/~yifanhu/PUB/map_color.pdf Luckily, the authors discuss your question in Section 2 (yes, it is computationally hard, and it seems to have more than one name.).
