CLIQUE alami ke pengurangan k-Color

Jelas ada pengurangan dari CLIQUE ke k-Color karena keduanya NP-Complete. Bahkan, saya bisa membuat satu dengan menyusun pengurangan dari CLIQUE ke 3-SAT dengan pengurangan dari 3-SAT ke k-Color. Yang saya bertanya-tanya adalah apakah ada pengurangan langsung yang masuk akal antara masalah-masalah ini. Katakanlah, pengurangan yang bisa saya jelaskan kepada seorang teman cukup singkat tanpa perlu menggambarkan bahasa perantara seperti SAT.

Sebagai contoh dari apa yang saya cari, berikut adalah pengurangan langsung ke arah sebaliknya: Diberikan G dengan dan beberapa (jumlah warna), buat grafik G 'dengan simpul (satu per warna per simpul). Verteks , sesuai dengan simpul dan warna masing-masing berbatasan jika dan hanya jika dan ( atau ). Sebuah -clique di hanya memiliki satu simpul per simpul dalam , dan warna yang sesuai adalah -color yang tepat darin k k n v ′ u ′ v , u c , d v ≠ u c ≠ d v u ∉ G n G ′ G k $n$$k$$kn$$v'$$u'$$v, u$$c, d$$v \neq u$$c \neq d$$vu \not \in G$$n$$G'$$G$$k$$G$. Demikian pula, setiap tepat dari memiliki klik yang sesuai dalam .k G G $k$$G$$G'$

Sunting : Untuk menambahkan beberapa motivasi singkat, 21 masalah asli Karp dibuktikan NP-Complete oleh pohon reduksi di mana CLIQUE dan Chromatic Number membentuk akar dari subpohon utama. Ada beberapa pengurangan alami antara masalah pada subtree CLIQUE dan subtree Chromatic Number, tetapi banyak dari mereka yang sulit ditemukan seperti yang saya tanyakan. Saya mencoba menelusuri apakah struktur pohon ini menunjukkan beberapa struktur yang mendasari pada masalah lain atau apakah itu sepenuhnya merupakan konsekuensi dari pengurangan yang ditemukan pertama kali, karena ada sedikit motivasi untuk mencari pengurangan antara dua masalah ketika mereka diketahui berada di kelas kompleksitas yang sama. Tentu saja tatanan itu memiliki pengaruh, dan bagian-bagian pohon dapat ditata ulang, tetapi dapatkah ditata ulang secara sewenang-wenang?

Sunting 2 : Saya terus mencari pengurangan langsung, tapi di sini ada sketsa yang terdekat dengan yang saya dapatkan (seharusnya pengurangan yang valid, tetapi memiliki CIRCUIT SAT sebagai perantara yang jelas; agak subjektif apakah ini lebih baik daripada menyusun dua pengurangan sebagaimana disinggung dalam paragraf pertama).

Mengingat , kita tahu bahwa dapat berupa -warna dengan simpul semua berwarna True iff memiliki -clique. Kami nama simpul asli dan kemudian tambahkan ke simpul tambahan: dengan , . Invarian kunci adalah bahwa dapat diwarnai True jika dan hanya jika di antara simpul setidaknya ada simpul berwarna True. Jadi, setiap dapat Benar. Kemudian,G , k ¯ G n - k + 1 k G k G v 1 , … , v n ¯ G C i j 1 ≤ i ≤ n 0 ≤ j ≤ k C i j { v 1 , … , v i } j C i 0 C i $G, k$$\overline{G}$$n-k+1$$k$$G$$k$$G$ $v_1, \ldots, v_n$$\overline G$$C_{ij}$$1 \le i \le n$$0 \le j \le k$$C_{ij}$$\{v_1,\ldots, v_i\}$$j$$C_{i0}$$C_{ij}$ untuk mendapatkan warna mana semua warna yang tidak benar diperlakukan sebagai salah. Ada -clique di iff dapat diwarnai True, jadi jika kita memaksakan pewarnaan itu, grafik baru akan berwarna jika ada -clique dalam grafik asli.j > 0 C ( i - 1 ) j ∨ C ( i - 1 ) ( j - 1 ) ∧ v i k G C n k$j > 0$$C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$$k$$G$$C_{nk}$$k$

Gadget AND dan OR untuk menegakkan hubungan sangat mirip dengan pengurangan dari CIRCUIT SAT menjadi 3-COLOR, tetapi di sini kami menyertakan dalam grafik kami, pilih simpul T, F, dan Ground, lalu sambungkan semua yang lain ke semuanya kecuali ; ini memastikan bahwa s dan gadget lainnya hanya menerima 3 warna.K n - k + 1 v i C i $K_{n-k+1}$$v_i$$C_{ij}$

Bagaimanapun, bagian dari pengurangan ini terasa langsung, tetapi penggunaan gerbang AND / OR jauh lebih tidak langsung. Pertanyaannya tetap, apakah ada pengurangan yang lebih elegan?$\overline G$

Sunting 3 : Ada beberapa komentar tentang mengapa pengurangan ini sulit ditemukan. CLIQUE dan k-Color memang masalah yang sangat berbeda. Meskipun tanpa pengurangan, sekalipun, jawaban yang merinci mengapa pengurangan sulit di satu arah tetapi mungkin di sisi lain akan sangat membantu dan berkontribusi banyak untuk masalah ini.

Mengingat grafik G dan sejumlah k , sehingga Anda ingin tahu apakah G mengandung k -clique, biarkan n adalah jumlah simpul di G . Kami membuat grafik H lainnya , sehingga H adalah n -colorable jika dan hanya jika G memiliki k -clique, sebagai berikut:$G$$k$$G$$k$$G$$H$$H$$n$$G$$k$

(1) Untuk setiap simpul v dalam G , buat n -simpul simpul ( v , i ) dalam H , di mana i berkisar dari 1 hingga n .$v$$G$$n$$(v,i)$$H$$i$$1$$n$

(2) Tambahkan satu tambahan simpul x ke H .$x$$H$

(3) Untuk setiap rangkap tiga { x , y , z } dari simpul dalam H , di mana y = ( v , i ) dan z = ( u , j ) , uji apakah salah satu dari kondisi berikut ini berlaku: baik u ≠ v dan i = j , atau u dan v adalah simpul yang tidak berdekatan dalam G dengan maks ( i , j ) ≤ $\{x,y,z\}$$H$$y=(v,i)$$z=(u,j)$$u\ne v$$i=j$$u$$v$$G$$\max(i,j)\le k$. Jika salah satu dari dua hal ini benar, menambah n -clique ke H . Dalam klik ini, pilih tiga simpul x ′ , y ′ , dan z ′ . Hubungkan x ke setiap simpul dalam klik kecuali untuk y ′ dan z ′ ; hubungkan y ke setiap simpul dalam klik kecuali untuk x ′ dan z ′ ; dan hubungkan z ke setiap simpul dalam klik kecuali untuk x ′ dan y ′ .$n$$H$$x'$$y'$$z'$$x$$y'$$z'$$y$$x'$$z'$$z$$x'$$y'$

Gadget yang ditambahkan pada langkah (3) mencegah triple dari simpul x , y , dan z dari semua diberi warna yang sama satu sama lain dalam pewarnaan H yang valid . Klik di G dapat dipulihkan dari pewarnaan H sebagai himpunan simpul ( v , i ) yang berada dalam kelas warna yang sama dengan x dan yang memiliki i ≤ k .$x$$y$$z$$H$$G$$H$$(v,i)$$x$$i\le k$

?? pewarnaan dan penemuan klik telah dikenal sangat erat selama beberapa dekade melalui teori grafik (mungkin bahkan di tahun 60an?) bahkan tidak melalui SAT sebagai perantara (yang menjadi khas setelah bukti Cook pada tahun 1971). percaya ada algoritma berdasarkan pada properti dasar berikut :

Jika G berisi klik ukuran k, maka setidaknya k warna diperlukan untuk mewarnai klik itu; dengan kata lain, bilangan kromatik setidaknya adalah bilangan klik: $\chi(G) \ge \omega(G).\,$

tidak yakin dengan referensi yang tepat tetapi [1,2] adalah tempat yang baik untuk memulai, algoritma atau referensi yang tepat setidaknya mungkin dikutip dalam buku-buku ini.

[1] Klik, pewarnaan, & kepuasan, tantangan DIMAC ke-2

[2] Dimacs vol 26: Klik, pewarnaan, dan kepuasan