# On the complexity of Bandwidth Minimization

The graph bandwidth problem is defined as follows. Given a graph $G=(V,E)$, a layout $f$ of $G$ is a one-to-one mapping of the vertices of $G$ onto the integers $\{1, \ldots, |V|\}$. The bandwidth of $f$ is defined as

$bw(f) = \max \{|f(u) - f(v)| \mid \{u,v\} \in E\}$.

The bandwidth of $G$, denoted $bw(G)$, is defined as the minimum bandwidth of a layout, the minimum being taken over all possible layouts.

The decision question is: given a graph $G$ and an integer $k$, is $bw(G) \le k$?

This problem is known to be NP-complete even for trees of maximum degree three [Complexity Results for Bandwidth Minimization. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, No.3, 1978]. The authors show that one can test whether a graph has bandwidth at most two in polynomial time. The case $bw \le 3$ was open.

Is the complexity of the case $bw \le 3$ known? What do we know about the complexity of the problem when $k$ is not part of the input but a fixed constant at least $4$?

References would be nice.

The bandwidth problem is $W[t]$-hard for all $t$. It was shown by Bodlaender et al. in "Beyond NP-completeness for problems of bounded width." See the paper.
On the other hand, it is also known that for any $k$, whether a given graph has bandwidth at most $k$ can be decided in $O(f(k)n^{k+1})$ time. This implies that the bandwidth problem is in $XP$. See the another paper by Saxe.
• Yes, but this does not answer my question. The problem may be polynomial-time decidable for the case $bw \le 3$ and still be hard for every level of the $W$-hierarchy. Feb 3 '12 at 12:33
• Ok, my answer was not so complete. It is also known that for any $k$, whether a given graph has bandwidth at most $k$ can be decided in $O(f(k) n^{k+1})$ time for any $k$. This implies that the bandwidth problem is in $XP$. See the another paper by Saxe ( dx.doi.org/10.1137/0601042 ). Does this answer the remaining part of your question? Feb 3 '12 at 12:53