The complexity of the approximation of the bandwidth problem

The bandwidth problem has a long history and a number of important applications. It is the problem of enumerating the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. We will show for any constant kεN that there is no polynomial time approximation algorithm with an approximation factor of k. Furthermore, we will show that this result holds also for caterpillars, a class of restricted trees. We construct for any x,ε∈R with x>1 and ε>0 a graph class for which an approximation algorithm with an approximation factor of x+ε exists, but the approximation of the bandwidth problem within a factor of x-ε is NP-complete. The best previously known approximation factors for the intractability of the bandwidth approximation problem were 1.5 for general graphs and 4/3 for trees