14
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Somnath Feb 3 '12 at 12:33
  • 2
    $\begingroup$ 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? $\endgroup$ – Yota Otachi Feb 3 '12 at 12:53
  • 2
    $\begingroup$ I think that the paper by Saxe answers the question completely. Can you edit the answer to include it? $\endgroup$ – Tsuyoshi Ito Feb 3 '12 at 13:11
  • 1
    $\begingroup$ Yes, it does answer my question. Thanks much. $\endgroup$ – Somnath Feb 4 '12 at 9:49
  • 1
    $\begingroup$ by clicking the check-mark on the left of my answer :-) $\endgroup$ – Yota Otachi Feb 6 '12 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.