On Approximation Intractability of the Bandwidth Problem

The bandwidth problem 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. The problem has a long history and a number of applications. There was not much known though on approximation hardness of this problem, till recently. Karpinski and Wirtgen [KW 97] showed that there are no polynomial time approximation algorithms with an absolute error guarantee of n 1\\Gammaffl for any ffl ? 0 unless P = NP . In this paper we show, that there is no PTAS for the bandwidth problem unless P = NP , even for trees. More precisely we show that there are no polynomial time approximation algorithms for general graphs with an approximation ratio better than 1:5, and for the trees with an approximation ratio better than 4=3 ß 1:332.