<p>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 <a href="http://dx.doi.org/10.1145/195058.195229" rel="nofollow">the paper</a>.</p>

<p>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 <a href="http://dx.doi.org/10.1137/0601042" rel="nofollow">another paper</a> by Saxe.</p>

CC BY-SA 3.0
2012-02-03T12:33:23.173Z
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.
Somnath
CC BY-SA 3.0
2012-02-03T12:53:10.793Z
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 ( http://dx.doi.org/10.1137/0601042 ). Does this answer the remaining part of your question?
Yota Otachi
CC BY-SA 3.0
2012-02-03T13:11:39.543Z
I think that the paper by Saxe answers the question completely.  Can you edit the answer to include it?
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-03T13:17:39.000Z
The answer has been edited. Thanks Tsuyoshi.
Yota Otachi
CC BY-SA 3.0
2012-02-04T09:49:44.370Z
Yes, it does answer my question. Thanks much.
Somnath
CC BY-SA 3.0
2012-02-06T03:17:47.467Z
by clicking the check-mark on the left of my answer :-)
Yota Otachi
CC BY-SA 3.0
2012-02-03T12:23:50.690Z
2012-02-23T03:28:22.193Z
2012-02-23T03:28:22.193Z
Yota Otachi
<p>The graph bandwidth problem is defined as follows. Given a graph $G=(V,E)$, a <em>layout</em> $f$ of $G$ is a one-to-one mapping of the vertices of $G$ onto the integers $\{1, \ldots, |V|\}$. The <em>bandwidth of $f$</em> is defined as </p>

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

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

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

<p>This problem is known to be NP-complete even for trees of maximum degree three [<em><a href="http://www.jstor.org/pss/2100947">Complexity Results for Bandwidth Minimization</a>.</em> 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. </p>

<p>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$? </p>

<p>References would be nice.  </p>

<cc.complexity-theory>
On the complexity of Bandwidth Minimization
Somnath
# On the complexity of Bandwidth Minimization

(Asked by: username_0 on 2012-02-03)

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](http://www.jstor.org/pss/2100947).* 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.

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2012-02-03. Score: 16 | Accepted answer

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](http://dx.doi.org/10.1145/195058.195229).

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](http://dx.doi.org/10.1137/0601042) by Saxe.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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 ( http://dx.doi.org/10.1137/0601042 ). Does this answer the remaining part of your question?  
> **username_2**: I think that the paper by Saxe answers the question completely.  Can you edit the answer to include it?  
> **username_1**: The answer has been edited. Thanks Tsuyoshi.  
> **username_0**: Yes, it does answer my question. Thanks much.  
> **username_1**: by clicking the check-mark on the left of my answer :-)  

---

