Laying Out Sparse Graphs with Provably Minimum Bandwidth

Finding a linear layout of a graph having minimum bandwidth is a combinatorial optimization problem that has been studied since the 1960s. Unlike other classical problems, the approach based on stating a suitable integer linear program and solving the associated linear-programming relaxation seems to be useless in this case. This makes it nontrivial to design algorithms capable of solving to optimality instances of reasonable size. In this paper, we illustrate a new simple lower bound on the optimal bandwidth and its extension within an enumerative algorithm, leading to integer linear-programming relaxations that can be solved efficiently and provide effective lower bounds if part of the layout is fixed. Keeping the integrality constraints in these relaxations is essential for this purpose. We show that the resulting method can solve to proven optimality 24 out of the 30 instances from the literature with less than 200 nodes, each in less than a minute on a personal computer. The new approach is also analyzed on randomly generated instances with up to 1000 nodes. Moreover, we propose a method to compute the well-known density lower bound on the optimal bandwidth, which succeeds in finding this bound within minutes for most instances in the literature with up to 250 nodes.