Suppose you are given an undirected graph G. Define a layout of G to be a way of assigning distinct real-number coordinates to the vertices of G, so that the edges of G can be represented as (open) intervals of the real number line. Define the bandwidth of a layout to be the maximum number of such intervals covering any point of the real line. For instance, if G has vertices with coordinates 1,2,3,4, and edges (1,3) (2,3) (3,4) and (1,4), then the bandwidth of this layout is three, since three of the intervals cover the value 2.5.
The bandwidth of G itself is defined to be the minimum bandwidth of any layout of G. For instance, the layout above is not the best possible: the same graph has a layout with bandwidth two, so the bandwidth of G in this example is two. Two layouts are equivalent (and have the same bandwidth) if they form the same permutation of the vertices, so one can compute the bandwidth of G by generate and test in time O(n!).
The homework problem is to devise a more efficient dynamic programming algorithm for computing the bandwidth of a given graph.
Hint: if you choose to permute the vertices so that some subset S is placed with smaller coordinates than everything not in S, then what is the optimal layout of S, and what can you say about the overall bandwidth of the layout?