Graph ordering with smallest max vertex “discrepancy”

Question

Consider an undirected graph $G=(V,E)$ and a bijective function $f:V \rightarrow [|V|]$ which orders the vertices by mapping them onto the first $|V|$ natural numbers.

Define the cost of an ordering of a graph to be:

$$\text{cost}(G,f) = \max_{(u,v) \in E} f(u)-f(v)$$

(I refer to $f(u) - f(v)$ in the title as "discrepancy" to avoid confusion with terms such as length or distance)

Intuitively, if we were to construct $G$ by adding on one vertex at a time and adding the appropriate edges to the already-existing vertices, the cost is how far back in our list of vertices we'd have to go and add edges to.

Question: How difficult is the problem of minimizing this cost? Is there an efficient algorithm for finding an optimal ordering? Also is there a name for this cost that i'm not aware of?

Ideas:

A BFS ordering can do arbitrarily bad on this problem: Consider a complete binary tree -- the optimal cost is $O(\log N)$ but a BFS ordering can cost up to $O(N)$.

A DFS ordering can do arbitrarily bad on this problem: Consider a path graph modified such that each vertex is connected to an additional leaf vertex -- the optimal cost is $2$ but a DFS ordering can cost up to $O(N)$.

Answer 1

Your problem is known as BANDWIDTH. Another way to describe it is: we are given a matrix, and we want to rearrange the rows and columns (in the same way!) so that the only non-zero entries lie across a narrow band around the diagonal.

BANDWIDTH is known to be NP-complete. Unger showed that it is NP-hard to approximate to within any constant factor. Feige gave an $\tilde{O}(\log^3 n)$-approximation algorithm which uses metric embeddings.

Among the many variants of BANDWIDTH, let me mention the MINIMAL LINEAR ARRANGEMENT problem (known by various other names), in which the goal is to minimize $\displaystyle\sum_{(u,v) \in E} |f(u)-f(v)|$ rather than $\displaystyle\max_{(u,v) \in E} |f(u)-f(v)|$.