Sur la complexité de la minimisation de la bande passante

Le problème de bande passante du graphique est défini comme suit. Étant donné un graphe , une disposition de est un mappage un à un des sommets de sur les entiers . La largeur de bande de est définie comme$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\}$ .

La largeur de bande de $G$ , notée $bw(G)$ , est définie comme la largeur de bande minimale d'une disposition, le minimum étant pris en compte dans toutes les dispositions possibles.

La question de décision est: étant donné un graphe $G$ et un entier $k$ , est $bw(G) \le k$ ?

Ce problème est connu pour être NP-complet même pour les arbres de degré trois maximum [ Résultats de complexité pour la minimisation de la bande passante . Garey, Graham, Johnson et Knuth, SIAM J. Appl. Math., Vol. 34, n ° 3, 1978]. Les auteurs montrent que l'on peut tester si un graphe a une bande passante au plus deux en temps polynomial. L'affaire $bw \le 3$ était ouverte.

La complexité de l'affaire $bw \le 3$ connue? Que savons-nous de la complexité du problème lorsque $k$ ne fait pas partie de l'entrée mais une constante fixe au moins $4$ ?

Les références seraient bien.

Le problème de largeur de bande est -hard pour tout . Cela a été démontré par Bodlaender et al. dans "Au-delà de l'exhaustivité NP pour les problèmes de largeur limitée." Voir le papier .$W[t]$$t$

D'autre part, on sait également que pour tout , le fait qu'un graphe donné ait ou non une bande passante au plus peut être décidé en temps . Cela implique que le problème de bande passante est dans . Voir l' autre article de Saxe.$k$$k$$O(f(k)n^{k+1})$$XP$