Dekomposisi Modular dan lebar-klik

Saya mencoba memahami beberapa konsep tentang dekomposisi modular dan grafik lebar-klik .

Dalam makalah ini ("Pada grafik P4-rapi"), ada bukti bagaimana menyelesaikan masalah optimasi seperti angka-klik atau angka-kromatik menggunakan dekomposisi Modular. Memecahkan masalah ini dengan menyusun (menggunakan jumlah disjoint atau disjoint union) dua grafik G1, G2 mudah ketika Anda tahu jawaban untuk G1 dan G2. Karena grafik utama pada dekomposisi grafik P4-rapi adalah grafik terikat (yaitu C5, P5, dll.), Mudah untuk menyelesaikannya untuk "kasus dasar" ini dan kemudian menyelesaikannya untuk komposisi. Oleh karena itu dengan menggunakan pohon dekomposisi dimungkinkan untuk menyelesaikan masalah ini dalam waktu linier.

Tetapi tampaknya teknik ini akan bekerja dengan kelas grafik apa pun sehingga grafik-bilangan prima dibatasi. Kemudian saya menemukan makalah ini "Masalah Waktu Optimasi Solvable Linear pada Grafik Lebar Klik Terikat" yang tampaknya membuat generalisasi yang saya cari tetapi saya tidak bisa memahaminya dengan baik.

Pertanyaan saya adalah:

1- Apakah sama dengan mengatakan bahwa grafik utama dari pohon dekomposisi dibatasi (seperti dalam kasus grafik P4-rapi) dan mengatakan bahwa grafik memiliki properti "Clique-Width" dibatasi?

2 - Dalam hal jawaban untuk 1 adalah TIDAK, maka: Apakah ada hasil apapun tentang kelas grafik dengan grafik-bilangan prima terikat (seperti dalam grafik P4-rapi) dan dengan demikian masalah optimasi seperti angka-klik yang dapat dipecahkan pada waktu linier pada semua kelas ini ?

Anda akan menemukan teks pengantar pada lebar klik (cwd untuk pendek) di sini: Batas atas dengan lebar klik grafik (B. Courcelle dan S. Olariu, DAM 101). Anda dapat menemukan hasil yang lebih baru dalam survei ini: Perkembangan terkini pada grafik lebar klik terbatas (M. Kaminski, V. Lozin, M. Milanic, DAM 157 (12): 2747-2761 (2009))

Cwd adalah ukuran kompleksitas berdasarkan operasi grafik yang menggeneralisasi gabungan kata. Grafik yang tak terhitung jumlahnya dapat dibatasi cwd. Anda akan mengatakan bahwa satu set (mungkin tak terbatas) grafik (terbatas atau dapat dihitung) telah membatasi cwd jika ada konstanta k sedemikian sehingga setiap grafik di set ini memiliki cwd paling banyak k. Misalnya, grafik lengkap memiliki cwd 2, grafik herediter jarak cwd paling banyak 3, ...

1) Tautan antara cwd dan modular-dec adalah sebagai berikut: cwd (G) = max {cwd (H) | H prima dalam dek modular G}. Oleh karena itu, Anda dapat mengatakan bahwa cwd menggeneralisasikan fakta bahwa "grafik utama telah membatasi ukuran". Anda dapat memiliki grafik dengan prima-grafik dengan ukuran tidak terbatas tetapi dengan cwd terbatas.

2) jika ukuran prime-graphs dibatasi, cwd dibatasi. Hasil dalam makalah yang Anda kutip mengatakan bahwa masalah yang dapat diekspresikan dalam MSOL dapat diselesaikan secara efisien dalam kelas grafik cwd terbatas. Set masalah ini mencakup banyak masalah NP-lengkap: nomor-klik, angka stabil, 3-warna, ...

Beberapa aspek algoritmik dari dek modular dipelajari di sini "Sebuah survei dari aspek algoritmik dekomposisi modular" (M. Habib dan C. Paul, Ilmu Komputer Review 4 (1): 41-59 (2010))