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 a

O

(

n

O

(

t

)

2

n

) exact algorithm. Moreover for the same class of graphs we introduce a subexponential constant-approximation scheme – for any

α

> 0 there exists a (1 + 

α

)-approximation algorithm running in

$O(\exp(c(t + \sqrt{n/\alpha})\log n))$

time where

c

is a universal constant. These results seem interesting since Unger has proved that

Bandwidth

does not belong to

APX

even when the input graph is a tree (assuming

P

 ≠ 

NP

). So somewhat surprisingly, despite Unger’s result it turns out that not only a subexponential constant approximation is possible but also a subexponential approximation scheme exists. Furthermore, for any positive integer

r

, we present a (4

r

 − 1)-approximation algorithm that solves

Bandwidth

for an arbitrary input graph in

$O^*(2^{n\over r})$

time and polynomial space. Finally we improve the currently best known exact algorithm for arbitrary graphs with a

O

(4.473

n

) 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

*

(2

n

) time and space, what matches the best known results.