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