Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time

Abstract

In this paper we investigate the problem of testing the bandwidth of a graph: Given a graph, G, can the vertices of G be mapped to distinct positive integers so that no edge of G has its endpoints mapped to integers which differ by more than some fixed constant, k? We exhibit an algorithm to solve this problem in $O ( f ( k )N^{k + 1} )$ time, where N is the number of vertices of G and $f ( k )$ depends only on k. This result implies that the “Bandwidth $\overset{?}{\leqq} k$” problem is not NP-complete (unless P = NP) for any fixed k, answering an open question of Garey, Graham, Johnson, and Knuth. We also show how the algorithm can be modified to solve some other problems closely related to the “Bandwidth $\overset{?}{\leqq} k$” problem.