Parameterized Complexity of Bandwidth on Trees

The bandwidth of a n-vertex graph G is the smallest integer b such that there exists a bijective function f: V (G) → {1,..., n}, called a layout of G, such that for every edge uv ∈ E(G), |f(u) − f(v) | ≤ b. In the Bandwidth problem we are given as input a graph G and integer b, and asked whether the bandwidth of G is at most b. We present two results concerning the parameterized complexity of the Bandwidth problem on trees. First we show that an algorithm for Bandwidth with running time f(b)n o(b) would violate the Exponential Time Hypothesis, even if the input graphs are restricted to be trees of pathwidth at most two. Our lower bound shows that the classical 2 O(b) n b+1 time algorithm by Saxe [SIAM Journal on Algebraic and Discrete Methods, 1980] is essentially optimal. Our second result is a polynomial time algorithm that given a tree T and integer b, either correctly concludes that the bandwidth of T is more than b or finds a layout of T of bandwidth at most b O(b). This is the first parameterized approximation algorithm for the bandwidth of trees.