Apakah masalah himpunan dominan terbatas pada grafik bipartit planar dengan NP-degree maksimum 3?

Apakah ada yang tahu tentang hasil kelengkapan NP untuk masalah SET DOMINASI dalam grafik, terbatas pada kelas grafik bipartit planar dengan derajat 3 maksimum?

Saya tahu ini adalah NP-lengkap untuk kelas grafik planar tingkat maksimum 3 (lihat buku Garey dan Johnson), serta untuk grafik bipartit tingkat maksimum 3 (lihat M. Chlebík dan J. Chlebíková, "Kekerasan perkiraan mendominasi masalah himpunan dalam grafik derajat terbatas "), tetapi tidak dapat menemukan kombinasi keduanya dalam literatur.

Bagaimana jika Anda cukup melakukan hal berikut: Diberikan grafik , buat grafik lain G ′ = ( V ∪ U , E ′ ) dengan membagi setiap tepi G dalam 4 bagian; di sini U adalah himpunan node baru yang kami perkenalkan, dan | U | = 3 | E | .$G = (V,E)$$G' = (V \cup U, E')$$G$$U$$|U| = 3|E|$

Grafik adalah bipartit. Apalagi jika G adalah planar dan memiliki maks. derajat 3, maka G ′ juga planar dan memiliki maks. derajat 3.$G'$$G$$G'$

Biarkan menjadi set (minimum) yang mendominasi untuk G ′ . Pertimbangkan tepi ( x , y ) ∈ E yang dibagi lagi untuk membentuk jalur ( x , a , b , c , y ) dalam G ′ . Sekarang jelas setidaknya satu dari a , b , c ada di D ′ . Selain itu, jika kita memiliki lebih dari satu dari a , b , c dalam D ′ , kita dapat memodifikasi$D'$$G'$$(x,y) \in E$$(x,a,b,c,y)$$G'$$a,b,c$$D'$$a,b,c$$D'$ sehingga ia tetap merupakan perangkat dominan yang valid dan ukurannya tidak bertambah. Sebagai contoh, jika kita memiliki sebuah ∈ D ' dan c ∈ D ' , kita bisa sama-sama baik menghapus c dari D ' dan menambahkan y ke D ' . Oleh karena itu wlog kita memiliki | D ′ ∩ U | = | E | .$D'$$a \in D'$$c \in D'$$c$$D'$$y$$D'$$|D' \cap U| = |E|$

Kemudian mempertimbangkan . Asumsikan x ∈ V dan x ∉ D ′ . Maka kita harus memiliki simpul a ∈ D ′ sedemikian rupa sehingga ( x , a ) ∈ E ′ . Karenanya ada tepi ( x , y ) ∈ E sedemikian sehingga kita memiliki jalur ( x , a , b , c , y ) dalam G $D = D' \cap V$$x \in V$$x \notin D'$$a \in D'$$(x,a) \in E'$$(x,y) \in E$$(x,a,b,c,y)$$G'$. Karena dan a ∈ D ′ , kita memiliki b , c ∉ D ′ , dan untuk mendominasi c kita harus memiliki y ∈ D ′ . Oleh karena itu di G simpul y adalah tetangga dari x dengan y ∈ D . Artinya, D adalah satu set mendominasi untuk G .$a,b,c \in U$$a \in D'$$b, c \notin D'$$c$$y \in D'$$G$$y$$x$$y \in D$$D$$G$

Sebaliknya, pertimbangkan (minimum) mendominasi set untuk G . Membangun satu set mendominasi D ' untuk G ' sehingga | D ′ | = | D | + | E | sebagai berikut: Untuk tepi ( x , y ) ∈ E yang dibagi lagi untuk membentuk jalur ( x , a , b , c , y ) di G ′ , kami menambahkan a ke$D$$G$$D'$$G'$$|D'| = |D| + |E|$$(x,y) \in E$$(x,a,b,c,y)$$G'$$a$ jika x ∉ D dan y ∈ D ; kita menambahkan c ke D ′ jika x ∈ D dan y ∉ D ; dan kalau tidak kita tambahkan b ke D ′ . Sekarang dapat diperiksa bahwa D ′ adalah set yang mendominasi untuk G ′ : Dengan konstruksi, semua node di U didominasi. Sekarang, biarkan x ∈ V ∖ D ′ . Lalu ada y ∈ V sedemikian rupa$D'$$x \notin D$$y \in D$$c$$D'$$x \in D$$y \notin D$$b$$D'$$D'$$G'$$U$$x \in V \setminus D'$$y \in V$ , dan karenanya sepanjang jalan ( x , a , b , c , y ) kita memiliki sebuah ∈ D ' , yang mendominasi x .$(x,y) \in E$$(x,a,b,c,y)$$a \in D'$$x$

Singkatnya, jika memiliki sekumpulan ukuran k yang mendominasi , maka G ′ memiliki sekumpulan ukuran yang mendominasi paling banyak k + | E | , dan jika G ′ memiliki set ukuran k + | yang mendominasi E | , maka G memiliki sekumpulan ukuran yang paling banyak mendominasi k .$G$$k$$G'$$k + |E|$$G'$$k + |E|$$G$$k$

Sunting: Menambahkan ilustrasi. Atas: grafik asli ; tengah: grafik G ′ dengan himpunan mendominasi "dinormalisasi"; bawah: grafik G ′ dengan himpunan dominan yang berubah-ubah.$G$$G'$$G'$