Kompleksitas masalah himpunan mendominasi dalam subclass spesifik grafik chordal

Saya tertarik pada kompleksitas masalah set mendominasi (DSP) di beberapa kelas grafik tertentu yang merupakan subkelas dari grafik chordal .

Grafik adalah grafik lintasan yang tidak diarahkan jika itu adalah grafik persimpangan-simpul dari keluarga lintasan di beberapa pohon yang tidak diarahkan. Biarkan UP menjadi kelas grafik jalur yang tidak diarahkan.

Grafik adalah grafik EPT jika itu adalah grafik persimpangan-sisi dari keluarga jalur di beberapa pohon yang tidak diarahkan. Grafik EPT mungkin bukan chordal, tetapi biarkan CEPT menjadi kelas grafik EPT chordal.

Grafik adalah grafik jalur terarah (yang berakar) jika itu adalah grafik persimpangan-simpul dari keluarga jalur berarah di beberapa pohon berarah yang di-root (yaitu semua busur diarahkan menjauh dari root). Biarkan RDP menjadi kelas grafik jalur terarah (yang di-root).

Kami memiliki $RDP\subseteq CEPT \subseteq UP\subseteq chordal$

Diketahui bahwa DSP adalah linear-time solvable untuk grafik dalam RDP tetapi NP-complete untuk grafik UP [ Booth dan Johnson, 1981 ]

Saya tertarik pada grafik khusus yang berhubungan dengan grafik persimpangan-titik keluarga dari jalur yang tidak diarahkan pada pohon seperti ulat dengan derajat maksimum 3. Lebih tepatnya, "ulat" ini dibangun dari jalur di mana setiap simpul kedua memiliki derajat liontin. satu titik terlampir. Mari kita sebut kelas ini cat-UP.

Selain itu, grafik khusus saya juga dapat dibangun sebagai grafik persimpangan-tepi dari beberapa keluarga jalur tidak berarah di pohon tertentu dengan derajat maksimum 3.

Jadi pertanyaan saya adalah:

1) Apakah kompleksitas DSP untuk grafik cat-UP diketahui? (perhatikan bahwa pengurangan [ Booth dan Johnson, 1981 ] menghasilkan pohon inang dengan derajat maksimum 3, tetapi cukup jauh dari ulat)

2) Apa kompleksitas DSP untuk grafik CEPT? Dan untuk grafik CEPT yang muncul dari pohon host tingkat maksimum 3? ( ini tidak diketahui oleh ISGCI )

3) Apakah ada hasil kompleksitas untuk DSP dalam keluarga grafik terkait erat?

Sayang sekali Anda telah menunggu begitu lama tanpa mendapatkan jawaban. Saya tidak tahu untuk kelas yang Anda minta, tetapi saya tahu beberapa kelas grafik terkait dan teknik baru yang dapat Anda coba.

Pertama saya akan menyebutkan bahwa Steven Chaplick telah melakukan pekerjaan pada kelas grafik terkait, ia menyelesaikan tesisnya awal tahun ini, Anda mungkin menemukan penelitiannya menarik.

Saya tahu beberapa hasil dalam arah ini mengikuti dari pekerjaan saya sendiri Kelas Grafik dengan Lingkungan Terstruktur dan Aplikasi Algoritma Ini memberikan teknik umum untuk menyelesaikan berbagai masalah termasuk DSP di kelas grafik tertentu. Kami melakukan ini dengan memperkenalkan dekomposisi grafik baru (lihat tesis saya ).

Sebagai contoh jika kita memberikan model persimpangan UP di mana pohon memiliki derajat max d dan jalur memiliki panjang max s kita dapat menyelesaikan dominasi set di $(d-1)^{3(s-1)}poly(n)$.

Mirip jika kita memiliki grafik yang diberikan dengan model persimpangan yang terdiri dari $0$jalur -bend di $k \times n$ kisi (untuk k konstan).

Teknik yang sama mungkin bekerja untuk CEPT yang muncul dari pohon host tingkat maksimum 3, tapi saya perlu lebih banyak waktu untuk memahami kelas ini. Jika Anda memiliki tautan ke beberapa penokohan di kelas ini, itu akan membantu.