Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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

share|cite|improve this question
At the risk of sending you on a 200-page wild goose chase, I'd suggest taking a look at Joe Gallian's Dynamic Survey of Graph Labeling, – Barry Cipra Nov 4 '11 at 20:36
It might help if you made some comments about where the problem comes from. My guess is that it is not particularly tractable algorithmically. – Igor Rivin Nov 4 '11 at 21:28

2 Answers 2

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.

share|cite|improve this answer
For a quick introduction, with references, see – Barry Cipra Nov 4 '11 at 23:00

For a very similar problem, see Luckily, the authors discuss your question in Section 2 (yes, it is computationally hard, and it seems to have more than one name.).

share|cite|improve this answer

Your Answer


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.