Algoritma Tepat untuk R-Dominasi Set pada Grafik Treewidth Terikat

Mengingat grafik, $G = (V, E)$ , saya ingin menemukan optimal $r$ -domination untuk $G$ . Artinya, saya ingin subset $S$ dari sehingga semua simpul di berada pada jarak paling dari beberapa titik di , dan meminimalkan ukuran .G r S $V$$G$$r$$S$$S$

Dari apa yang saya periksa sejauh ini, saya mendapatkan yang berikut: Ada masalah terkait ini untuk menemukan -center dalam grafik yang merupakan subset ukuran paling banyak sehingga semua simpul dalam grafik adalah pada jarak paling jauh dari beberapa titik di (di sini baik dan adalah bagian dari input) dimana Demaine et al . memiliki algoritma FPT untuk grafik planar. Kalau tidak, masalahnya adalah -hard untuk genap .S k r S | S | ≤ k r W [ 2 ] r = $(k,r)$$S$$k$$r$$S$$|S| \leq k$$r$$W[2]$$r = 1$

Adakah yang diketahui tentang kerumitan pasti masalah dominasi untuk grafik lebar pohon yang dibatasi atau bahkan hanya pohon? (Apakah dominasi MSO dapat didefinisikan? Masalah mendominasi yang biasa adalah MSO dapat didefinisikan - yang kemudian akan memungkinkan seseorang untuk menggunakan teorema Courcelle untuk menyimpulkan bahwa ada algoritma waktu linear untuk masalah tersebut). Apakah ada hasil kekerasan bersyarat yang diketahui mengenai masalah ini?r $r$$r$$k$

dominasi (optimal) untuk G adalah dominasi (optimal) untuk r daya G r dan sebaliknya ( G r diperoleh dari G dengan menambahkan tepi baru antara simpul jarak yang berbeda paling banyak r ).$r$$G$$r$$G^r$$G^r$$G$$r$

Fakta-fakta berikut diketahui dengan baik: (1) Semua kekuatan grafik chordal kuat sangat chordal (A. Lubiw, tesis Master; lihat juga Dahlhaus & Duchet, Pada grafik chordal yang sangat kuat, Ars Combin. 24 B (1987) 23-30 ), dan (2) Dominasi dapat dipecahkan dalam waktu linier untuk grafik chordal kuat (M. Farber. Dominasi, dominasi independen dan dualitas dalam grafik chordal kuat, Discrete Appl. Math., 7 (1984) 115-130). Karenanya dominasi dapat dipecahkan dalam waktu polinomial untuk grafik yang sangat chordal, khususnya untuk pohon ( r tetap atau tidak).$r$$r$

Gurski & Wanke terbukti di makalah ini bahwa kelompok-lebar adalah paling 2 ⋅ ( r + 1 ) tw ( G ) + 1 - 2 , di mana tw ( G ) adalah pohon-lebar G . Dengan demikian, untuk r tetap , kekuatan ke- r dari grafik lebar pohon terbatas telah membatasi lebar-klik. Oleh karena itu, untuk r tetap , r- dominasi dapat dipecahkan dalam waktu polinomial untuk grafik lebar pohon yang dibatasi (oleh teorema Courcelle). $G^r$$2\cdot (r+1)^{\text{tw}(G)+1}−2$$\text{tw}(G)$$G$$r$$r$$r$$r$

Sangat mudah untuk melakukan pemrograman dinamis pada grafik treewidth untuk masalah ini. Satu dapat menjaga untuk setiap simpul dalam kantong jarak terpendek ke beberapa simpul dalam solusi parsial dan jarak ke solusi masa depan yang diperlukan untuk mendominasi simpul tidak berdominasi.$k$

Ini total memberikan ukuran tabel jadi untuk tetap r masalah ini adalah FPT parameter dengan treewidth, namun jika r tidak tetap ini menjadi sebuah algoritma XP. Sejauh yang saya tahu pertanyaan apakah masalah ini FPT untuk semua nilai r terbuka.$O(r^k)$$r$$r$$r$

Dawar dan Kreutzer telah menunjukkan bahwa masalahnya adalah traktat parameter-tetap di kelas graf padat mana pun, yang mencakup grafik planar, grafik lebar pohon terbatas (lokal) dan semua kelas dengan anak di bawah umur (lokal) yang dikecualikan.

Dvorak telah menunjukkan bahwa ada perkiraan faktor konstanta waktu polinomial untuk kelas ekspansi terbatas, yang mencakup grafik planar, grafik lebar pohon terbatas dan semua kelas dengan anak di bawah umur yang dikecualikan.

Ada makalah baru-baru ini oleh Glencora Borradaile, Hung Le: Program Dinamik Optimal untuk r-Dominasi Masalah atas Dekomposisi Pohon (IPEC 2016). Di sini mereka menunjukkan bahwa ada algoritma yang diberikan sebagai input grafik , bilangan bulat r , dan dekomposisi pohon G lebar w , menghitung set r yang optimal untuk mendominasi G dalam waktu O ( ( 2 r + 1 ) w n ) . Selain itu, mereka menunjukkan bahwa ini adalah yang terbaik yang dapat dilakukan, dalam arti berikut: algoritma dengan waktu berjalan O ( ( $G$$r$$G$$w$$r$$G$$O((2r+1)^wn)$ untuk ε > 0 akan bertentangan dengan kuat eksponensial Waktu Hipotesis.$O((2r+1-\epsilon)^wn^{O(1)})$$\epsilon > 0$

Algoritme sekuensial linier untuk menghitung dominasi-r yang optimal untuk sebuah pohon disebabkan oleh Slater:

P. Slater. Dominasi R dalam grafik. J. ACM, 23 (3): 446–450, Juli 1976. doi: 10.1145 / 321958.321964

Algoritma terdistribusi untuk pengaturan yang sama adalah karena Turau dan Köhler:

Volker Turau dan Sven Köhler. Algoritma Terdistribusi untuk Dominasi Jarak-k Minimum di Pohon. Jurnal Grafik Algoritma dan Aplikasi, 19 (1): 223–242,5 (lihat http://jgaa.info/getPaper?id=354 )