Pada kompleksitas Minimalkan Bandwidth

Masalah lebar pita grafik didefinisikan sebagai berikut. Diberikan grafik , tata letak dari adalah pemetaan satu-ke-satu dari simpul ke dalam bilangan bulat . The bandwidth didefinisikan sebagai$G=(V,E)$ $f$$G$$G$$\{1, \ldots, |V|\}$$f$

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

The bandwidth $G$ , dinotasikan $bw(G)$ , didefinisikan sebagai bandwidth minimum dari layout, minimum diambil alih semua layout mungkin.

Pertanyaan keputusannya adalah: diberi grafik $G$ dan integer $k$ , apakah $bw(G) \le k$ ?

Masalah ini dikenal sebagai NP-lengkap bahkan untuk pohon dengan derajat tiga maksimum [ Hasil Kompleksitas untuk Minimalkan Bandwidth . Garey, Graham, Johnson dan Knuth, SIAM J. Appl. Matematika., Vol. 34, No.3, 1978]. Para penulis menunjukkan bahwa seseorang dapat menguji apakah grafik memiliki bandwidth paling banyak dua dalam waktu polinomial. Kasus $bw \le 3$ terbuka.

Apakah kompleksitas kasus $bw \le 3$ dikenal? Apa yang kita ketahui tentang kompleksitas masalah ketika $k$ bukan bagian dari input tetapi konstanta tetap setidaknya $4$ ?

Referensi akan menyenangkan.

Masalah bandwidth adalah $W[t]$ -hard untuk semua $t$ . Itu ditunjukkan oleh Bodlaender et al. dalam "Melampaui NP-kelengkapan untuk masalah lebar terikat." Lihat kertasnya .

Di sisi lain, juga diketahui bahwa untuk setiap , apakah grafik yang diberikan memiliki lebar pita paling banyak dapat diputuskan dalam waktu . Ini menyiratkan bahwa masalah bandwidth di . Lihat kertas lain oleh Saxe.$k$$k$$O(f(k)n^{k+1})$$XP$