Na złożoność minimalizacji przepustowości

Problem przepustowości wykresu jest zdefiniowany następująco. Biorąc pod uwagę wykres $G=(V,E)$ , A układ $f$ z jest mapowanie jeden do jednego z wierzchołków na całkowite . Pasma określa się jakoG { 1 , … , | V | } f$G$$G$$\{1, \ldots, |V|\}$$f$

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

Pasmo $G$ , oznaczoną $bw(G)$ jest zdefiniowany jako minimalna szerokość pasma układu minimalna przejmowane wszystkich możliwych układów.

Pytanie decyzyjne brzmi: biorąc pod uwagę wykres $G$ i liczbę całkowitą $k$ , czy $bw(G) \le k$ ?

Ten problem jest znany jako NP-zupełny nawet dla drzew o maksymalnym stopniu trzecim [ Wyniki złożoności dla minimalizacji przepustowości . Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, nr 3, 1978]. Autorzy pokazują, że można sprawdzić, czy wykres ma szerokość pasma co najwyżej dwa w czasie wielomianowym. Sprawa $bw \le 3$ była otwarta.

Czy złożoność sprawy $bw \le 3$ znane? Co wiemy o złożoności problemu, gdy $k$ nie jest częścią danych wejściowych, ale stałą stałą co najmniej $4$ ?

Referencje byłyby miłe.

Problem z przepustowością jest twardy dla wszystkich . Zostało to pokazane przez Bodlaender i in. w „Powyżej kompletności NP dla problemów z ograniczoną szerokością”. Zobacz artykuł .$W[t]$$t$

Z drugiej strony wiadomo również, że dla dowolnego , o tym, czy dany wykres ma szerokość pasma co najwyżej można zdecydować w czasie . Oznacza to, że problem z przepustowością występuje w . Zobacz kolejny artykuł Saxe.$k$$k$$O(f(k)n^{k+1})$$XP$