Bandwidth on AT-Free Graphs

Abstract

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G = (V, E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β : {1, . . . , |V |} → V such that for every edge uv ∈ E, |β −1 (u) − β −1 (v)| ≤ k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n · 2 O(k log k) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.