Exact and approximate bandwidth

In this paper we gather several improvements in the field of exact and approximate exponential time algorithms for the Bandwidth problem. For graphs with treewidth t we present an O(nO(t)2n) exact algorithm.Moreover, for any two positive integers k≥2,r≥1, we present a (2kr−1)-approximation algorithm that solves Bandwidth for an arbitrary input graph in time and polynomial space where by O∗ we denote the standard big O notation but omitting polynomial factors. Finally, we improve the currently best known exact algorithm for arbitrary graphs with an O(4.383n) time and space algorithm.In the algorithms for the small treewidth we develop a technique based on the Fast Fourier Transform, parallel to the Fast Subset Convolution techniques introduced by Björklund et al. This technique can be also used as a simple method of finding a chromatic number of all subgraphs of a given graph in O∗(2n) time and space, what matches the best known results.