NP-Hardness of the Bandwidth Problem on Dense Graphs

The bandwidth problem is the problem of numbering 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 and varied history and is known to be NP-hard Papadimitriou [Pa 76]. Recently for ffi -dense graphs a constant ratio approximation algorithm for this problem has been constructed in Karpinski, Wirtgen and Zelikovsky [KWZ 97]. In this paper we prove that the bandwidth problem on the dense instances remains NP -hard. Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by DFG Grant KA 673/4-1, by the ESPRIT BR Grants 7097 and EC-US 030, and by the Max-Planck Research Prize. Email: marek@cs.bonn.edu. y Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by the ESPRIT BR Grants 7097 and EC-US 030. Email: wirtgen@cs.bonn.edu 1 Introduction The bandwidth problem on graphs has a very long and interesting history cf. [CCDG 82]..