Forbidden Subgraphs of Graphs with Low Bandwidth

A layout of a graph G is an injective function f : V(G) → Z, and the bandwidth of a layout f is (G,f) = maxuv ∈ E(G) |f(u) - f(v)|. The bandwidth (G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P ≠ NP there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis there is no algorithm with running time f(k)no(k) to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014]. In this paper we show that bandwidth of general graphs is FPT-approximable. In particular we give an algorithm that takes as input a graph G and integer k, runs in time f(k)nO(1) for some function f, and either outputs a subtree T of G such that (T) ≥ k, or a layout f of G of bandwidth at most (1084 · 411 k · k4)4k. This resolves in the affirmative an open problem of Chung and Seymour [Discrete Mathematics, 1989], who asked whether the bandwidth of every graph G is upper bounded in terms of the maximum bandwidth of one of its subtrees. Our theorem leads to a forbidden subgraph characterization for graphs of bounded bandwidth, and can be seen as an analog for bandwidth of the classic grid minor theorem for treewidth, forbidden subtree theorem for pathwidth, and forbidden sub-path theorem for tree-depth.