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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • 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, 2012 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, 2012 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, 2012 at 13:11
  • 1
    $\begingroup$ Yes, it does answer my question. Thanks much. $\endgroup$
    – Somnath
    Feb 4, 2012 at 9:49
  • 1
    $\begingroup$ by clicking the check-mark on the left of my answer :-) $\endgroup$
    – Yota Otachi
    Feb 6, 2012 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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