Sobre la complejidad de la minimización de ancho de banda

El problema del ancho de banda del gráfico se define de la siguiente manera. Dado un gráfico , un diseño de es un mapeo uno a uno de los vértices de en los enteros . El ancho de banda de se define como$G=(V,E)$ G G { 1 , … , | V | } f$f$$G$$G$$\{1, \ldots, |V|\}$$f$

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

El ancho de banda de $G$ , denotado $bw(G)$ , se define como el ancho de banda mínimo de un diseño, el mínimo se toma sobre todos los diseños posibles.

La pregunta de decisión es: dado un gráfico $G$ y un entero $k$ , ¿es $bw(G) \le k$ ?

Se sabe que este problema es NP completo incluso para árboles de grado máximo tres [ Resultados de complejidad para la minimización del ancho de banda . Garey, Graham, Johnson y Knuth, SIAM J. Appl. Math., Vol. 34, nº 3, 1978]. Los autores muestran que uno puede probar si un gráfico tiene ancho de banda como máximo dos en tiempo polinómico. El caso $bw \le 3$ estaba abierto.

¿Se conoce la complejidad del caso $bw \le 3$ ? ¿Qué sabemos acerca de la complejidad del problema cuando $k$ no es parte de la entrada sino una constante fija al menos $4$ ?

Las referencias estarían bien.

El problema del ancho de banda es -hard para todo . Fue demostrado por Bodlaender et al. en "Más allá de la completitud NP para problemas de ancho acotado". Mira el periódico .$W[t]$$t$

Por otro lado, también se sabe que para cualquier , si un gráfico dado tiene ancho de banda como máximo se puede decidir en el tiempo . Esto implica que el problema del ancho de banda está en . Ver el otro artículo de Saxe.$k$$k$$O(f(k)n^{k+1})$$XP$