Apakah ada kelas grafik yang menarik di mana treewidth sulit (mudah) untuk dihitung?

Treewith adalah parameter grafik penting yang menunjukkan seberapa dekat grafik dari menjadi pohon (walaupun tidak dalam arti topologi yang ketat).

Sudah diketahui bahwa menghitung treewidth adalah NP-hard.

Adakah kelas alami grafik di mana treewidth sulit untuk dihitung?

Demikian pula:

Apakah ada kelas grafik yang menarik di mana perhitungan treewidth mudah? Jika ya, adakah properti / tes struktural yang dapat dieksploitasi? Yaitu, Grafik memiliki properti X ⇒ menghitung treewidth dari G ∈ P .$G$$X$ $\Rightarrow$$G \in \mathbf{P}$

Treewidth adalah NP-sulit untuk dihitung pada grafik co-bipartit, memang bukti NP-kekerasan asli treewidth dari Arnborg et al. menunjukkan ini. Selain itu, Bodlaender dan Thilikos menunjukkan bahwa NP-sulit untuk menghitung grafik grafik dengan derajat maksimum . Akhirnya, untuk setiap grafik treewidth minimal 2 , membagi kembali sebuah edge (yaitu, mengganti edge dengan derajat 2 vertex yang berdekatan dengan dua endpoint edge) tidak mengubah treeewidth dari grafik. Oleh karena itu NP-sulit untuk menghitung grafik bipartit 2-degenerasi dari ketebalan besar yang sewenang-wenang.$9$$2$$2$

Masalahnya adalah waktu polinomial yang dapat dipecahkan pada grafik chordal, grafik permutasi, dan lebih umum pada semua kelas grafik dengan jumlah polinomial dari klik-klik maksimal potensial, lihat makalah ini oleh Bouchitte dan Todinca. Perhatikan bahwa dalam makalah yang sama ditunjukkan bahwa himpunan dari klik-klik maksimum potensial dari suatu graf G dapat dihitung dari G pada waktu O ( | Π ( G ) | 2 ⋅ n O ( 1 ) ) . Juga, algoritma Bodlaender ini menentukan apakah $\Pi(G)$$G$$G$$O(|\Pi(G)|^2 \cdot n^{O(1)})$$G$ memiliki paling banyak dalam waktu 2 O $k$. Oleh karena itu, treewidth adalah polinomial waktu dipecahkan untuk grafik dari treewidthO((logn) 1 / 3 ).$2^{O(k^3)}n$$O((\log n)^{1/3})$

Ini adalah masalah terbuka yang luar biasa apakah menghitung grafik grafik planar adalah waktu polinomial yang dapat diselesaikan atau NP lengkap. Perlu dicatat bahwa parameter graph branchwidth terkait (yang selalu berada dalam faktor 1,5 dari treewidth) adalah waktu polinomial yang dapat dihitung pada grafik planar.