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)| ≤ 6. 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 6. 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(6))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.
展开▼
