NP-Kelengkapan dari Masalah Pewarnaan Grafik

Formulasi Alternatif

Saya datang dengan formulasi alternatif untuk masalah di bawah ini. Formulasi alternatif sebenarnya adalah kasus khusus dari masalah di bawah dan menggunakan grafik bipartit untuk menggambarkan masalah. Namun, saya percaya bahwa formulasi alternatif masih NP-keras. Formulasi alternatif menggunakan set terputus dari node masuk dan keluar yang menyederhanakan definisi masalah.

Diberikan keluar dan masuk node (merah dan biru masing-masing dalam gambar), dan satu set tentang ukuran dari bobot tepi antara simpul keluar dan masuk. Tujuan dari masalah ini adalah untuk mewarnai tepi tebal pada gambar sehingga untuk setiap node yang masuk, suatu kondisi berlaku.n w i j n × $n$$n$$w_{ij}$$n \times n$

Diberikan set dari simpul output, satu set dari simpul input, bobot antara dan untuk , dan konstanta positif , temukan jumlah minimum warna untuk tepi (tepi tebal pada gambar di atas) sehingga untuk semua ,{ I $\{ O_i \; | \; i=1 \dots n \}$n × n w i j ≥ 0 O i I j i , j = 1 ... n β e i i j = 1 ... $\{ I_i\; | \; i=1 \dots n \}$$n \times n$$w_{ij} \ge 0$$O_i$$I_j$$i,j=1 \dots n$$\beta$$e_{ii}$$j=1 \dots n$

$$\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}} \ge \beta$$

di mana menunjukkan warna tepi .e i $c(i)$$e_{ii}$

Formulasi Lama

Masalah berikut terlihat NP-sulit bagi saya, tetapi saya tidak bisa menunjukkannya. Setiap bukti / komentar untuk menunjukkan kekerasan atau kemudahannya dihargai.

Asumsikan adalah grafik terarah tertimbang lengkap dengan node dan edge. Misalkan menunjukkan bobot edge dan menunjukkan warna edge . Diberikan subset dari tepi dan konstanta positif tujuannya adalah: menemukan jumlah warna minimum sedemikian rupa sehingga untuk setiap :n n ( n - 1 ) w i j ≥ 0 i j c ( i j ) i j T ⊆ E β e i j ∈ $K_n=\langle V,E \rangle$$n$$n(n-1)$$w_{ij} \ge 0$$ij$$c(ij)$$ij$$T \subseteq E$$\beta$$e_{ij} \in T$

c(ij)≠c(ik

$$\frac{w_{ij}}{1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}} \ge \beta.$$ dan $$c(ij) \neq c(ik) \quad for \quad j \neq k$$

Harap dicatat bahwa dalam masalah di atas, hanya bagian tepi di perlu diwarnai. Itulah masalahnya dapat diselesaikan di .O ( | T | ! $T$$\mathcal{O}(|T|!)$

Memperbarui:

Setelah komentar Tsuyoshi Ito saya memperbarui masalahnya. Penyebutnya diubah dari menjadi . Oleh karena itu, penyebut mengandung bobot di luar juga. Itulah sebenarnya mengapa saya menyebutkan grafik lengkap dalam definisi.$1+\sum_{c(kj)=c(ij),k \neq i,e_{kj} \in T} w_{kj}$$1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}$$T$

Saya juga menambahkan kendala tambahan . Itu berarti, tepi keluar dari suatu simpul harus dari warna yang berbeda (tetapi warna yang masuk bisa sama selama ketidaksamaan berlaku). Puts ini intuitif batas bawah pada jumlah warna, yang merupakan tingkat keluar-maksimum node di .$c(ij) \neq c(ik) \quad for \quad j \neq k$$T$

Seperti yang Tsuyoshi sebutkan, 's, , dan adalah input untuk masalah dan warna edge adalah output. T $w_{ij}$$T$$\beta$

Pembaruan 2:

Masalah tidak memaksa tepi dan memiliki warna yang sama. e j $e_{ij}$$e_{ji}$

Cukup sederhana untuk menunjukkan bahwa formulasi alternatif adalah NP-hard. Pengurangan ini dari masalah pewarnaan vertex. Mengingat grafik G dengan simpul, kita membuat sebuah instance dari masalah di atas dengan keluaran simpul dan simpul masukan. Bobot ditetapkan sebagai berikut: Untuk semua , misalkan . Untuk , jika ada tepi antara vertex dan vertex , biarkan , jika tidak biarkan . Selain itu, biarkan .n n i w i i = 1 i ≠ j i j w i j = w j i = 1 w i j = w j i = 0 β = $n$$n$$n$$i$$w_{ii}=1$$i \neq j$$i$$j$$w_{ij}=w_{ji}=1$$w_{ij}=w_{ji}=0$$\beta=1$

Ini cukup jelas tetapi sulit untuk menggambarkan mengapa pengurangan itu benar. Biarkan menunjukkan contoh dari pewarnaan grafik dan menunjukkan contoh yang dikurangi dari masalah. Untuk menunjukkan reduksi di atas memberikan solusi yang benar, kita perlu menunjukkan bahwa (1) setiap pewarnaan yang valid untuk juga berlaku untuk . (2) jawaban yang diberikan oleh minimal untuk .R R C R $\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$

Jika dan adalah dua simpul yang berdekatan dari , maka mereka harus memiliki warna yang berbeda di . Itu karena jika dan berbatasan dan mereka memiliki warna yang sama, fraksi akan menghasilkan , di mana memiliki nilai positif. Karena itu, kondisinya tidak tahan. Selain itu, setiap pewarnaan yang valid (tetapi tidak harus minimal) untuk , juga merupakan pewarnaan yang valid untuk . Ini mengikuti fakta bahwa dalam pewarnaan yang valid darij C R i $i$$j$$\mathcal{C}$$\mathcal{R}$$i$$j$$\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}}$$\frac{1}{1+X}$$X$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$, setiap pasangan node yang berdekatan memiliki warna yang berbeda, sehingga syarat berlaku untuk semua tepi berwarna dalam solusi. Karena setiap pewarnaan adalah pewarnaan yang valid untuk , solusi minimal untuk harus menjadi solusi minimal untuk . Kalau tidak, ini bukan yang minimal karena solusi untuk memberikan solusi dengan jumlah warna yang lebih sedikit.$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{C}$

EDIT : Konstruksi di bawah ini tidak berfungsi, sesuai komentar Tsuyoshi Ito di bawah, itu tidak menegakkan bahwa . Saya meninggalkannya kalau-kalau itu awal yang berguna. Juga, tidak termasuk busur dengan bobot .$c(ij)=c(ji)$$T$$0$

Sepanjang garis yang disarankan Mohsen, mulailah dengan Pewarnaan Tepi, ubah grafik menjadi digraf pada set simpul yang sama di mana kita miliki dan dalam , beri semua busur (pada titik ini) bobot , lalu add dan ke dengan , set untuk dan .$G=(V,E)$$D=(V,A)$$\forall uv\in E$$(u,v)$$(v,u)$$A$$a \in A$$w_{a} = 1$$\forall xy \notin E$$(x,y)$$(y,x)$$A$$w_{xy}=w_{yx}=0$$\beta$$1$$T=A$

Maka kondisi hanya terpenuhi jika tidak ada dua busur peristiwa pada titik yang sama memiliki warna yang sama, mengabaikan busur yang berasal dari non-tepi dalam grafik asli (karena mereka memiliki bobot ). Pewarnaan ini kemudian dapat dikonversi kembali ke pewarnaan yang tepat untuk grafik asli.$0$

Secara teknis saya telah mengonversi masalah asli Anda menjadi masalah keputusan ("apakah grafiknya berwarna dengan warna ?"), Tetapi ini perlu dilakukan agar sesuai dengan dan itu secara efektif dapat dipertukarkan hingga polinomial.N $k$$NP$

Jadi saya pikir itu berhasil, atau apakah saya baru saja menunjukkan sesuatu yang lain menjadi ? ;)$NP$