The complexity of the approximation of the bandwidth problem

Abstract

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/spl epsiv/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,/spl epsiv//spl isin/R with x>1 and /spl epsiv/>0 a graph class for which an approximation algorithm with an approximation factor of x+/spl epsiv/ exists, but the approximation of the bandwidth problem within a factor of x-/spl epsiv/ 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.