Grafik 3-colorability dapat direduksi sendiri

Saya tertarik pada reducibilitas diri sendiri dari masalah Grafik 3-Coloralibity.

Definisi masalah Grafik 3-Coloralibity.

Mengingat sebuah grafik diarahkan tidak terdapat cara untuk mewarnai node merah, hijau, dan biru yang ada node yang berdekatan memiliki warna yang sama? $G$

Definisi reducibilitas diri.

Bahasa dapat direduksi sendiri jika ada mesin turing oracle TM sehingga dan untuk setiap input panjang , menanyakan oracle untuk kata-kata panjang paling banyak . $L$ $T$ $L=L(T^L)$ $x$ $n$ $T^L(x)$ $n-1$

Saya ingin menunjukkan dengan cara yang sangat ketat dan formal bahwa Graph 3-colorability dapat direduksi sendiri.

Bukti self-reducibility SAT dapat digunakan sebagai contoh ( self-reducibility SAT ).

Menurut pendapat saya, gagasan umum bukti reducibilitas diri sendiri dari Grafik 3-colorability berbeda dari bukti SAT reducibilitas diri dalam beberapa aspek.

SAT memiliki dua pilihan untuk setiap literal (benar atau salah) dan Grafik 3-kolorabilitas memiliki tiga pilihan (yaitu, merah hijau biru).
Pilihan SAT literal independen satu sama lain dan pilihan warna Grafik 3 daya warna sangat tergantung, setiap simpul yang berdekatan harus memiliki warna yang berbeda, properti ini berpotensi dapat membantu mengurangi iterasi di antara semua warna.

Ide umum pembuktian .

Mari kita tunjukkan dengan warna vertex , yang dapat mengambil salah satu dari nilai berikut (merah, hijau, biru). Tentukan grafik dari grafik dengan mewarnai titik sembarang , tetapkan menjadi' red 'dan letakkan grafik dengan simpul berwarna ke input oracle. Jika oracle menjawab 1, yang berarti bahwa grafik yang dimodifikasi masih 3-warna, simpan tugas saat ini dan mulai iterasi baru, dengan berbagai vertex dipilih secara sewenang-wenang, color vertex $c_{v_i}$ $v_i$ $G'$ $G$ $v_0$ $c_{v_0}$ $G'$ $v_0$ $v_1$ $v_1$ sesuai dengan warna dari simpul yang berdekatan. jika oracle menjawab 0, yang berarti tugas sebelumnya telah merusak 3 colorability, pilih warna yang berbeda dari set tiga warna, tetapi masih sesuai dengan warna dari simpul yang berdekatan.

Bukti sebelumnya tidak kuat secara matematika, pertanyaannya adalah bagaimana memperbaikinya dan membuatnya lebih formal dan matematis ketat. Sepertinya saya perlu lebih hati-hati membedakan kasus ketika simpul baru tidak memiliki tepi dengan simpul yang sudah berwarna dan ketika simpul baru berdekatan dengan simpul yang sudah berwarna.

Selain itu saya ingin membuktikan bahwa Grafik 3-colorability adalah self-reducible ke bawah.

Definisi bahasa yang dapat direduksi sendiri ke bawah.

Bahasa dikatakan dapat direduksi sendiri ke bawah jika memungkinkan untuk menentukan dalam waktu polinomial jika menggunakan hasil kueri terpendek. $A$ $x \in A$

Idenya tampaknya sederhana dan intuitif: mulai dengan mewarnai titik sembarang, dan pada setiap iterasi tambahkan satu lagi titik berwarna dan periksa dengan oracle apakah grafik masih 3-warna, jika tidak membalikkan pewarnaan sebelumnya dan memeriksa warna lain.

Tetapi bagaimana menulis buktinya dengan cara yang ketat dan lebih penting bagaimana menemukan penyandian grafik yang sesuai.

Singkatnya, saya ingin menunjukkan bahwa Grafik 3-colorability dapat direduksi sendiri dan dapat direduksi sendiri secara ketat dan formal.

Saya akan menghargai berbagi pemikiran Anda dengan kami.

Memperbarui:

reducibilitas diri sendiri ke bawah

Reducibilitas diri menurun diterapkan pada masalah keputusan dan itu menjawab masalah keputusan yang sama dengan input yang lebih pendek, pada akhir proses penurunan diri sendiri kita harus memiliki tugas warna yang tepat.

Setiap 3 - grafik berwarna dengan lebih dari tiga simpul, memiliki dua simpul dengan warna yang sama. Rupanya, hanya ada tiga warna dan lebih dari tiga simpul sehingga beberapa simpul yang tidak berdekatan mungkin memiliki warna yang sama. Jika kita menggabungkan dan dengan warna yang sama dengan hasil, kita masih memiliki grafik 3 - warna, hanya karena, jika grafik 3 - berwarna, maka ada hak penugasan semua simpul yang berdekatan dengan dan sesuai dengan warna yang sama dari , jadi dengan menggabungkan $G$ $x,y$ $x$ $y$ $x$ $y$ $x, y$ $x, y$ kita tidak perlu mengubah warna dari setiap simpul, kita hanya perlu menambahkan lebih banyak tepi antara simpul yang sudah berwarna dengan benar (saya tahu itu bukan penjelasan terbaik, saya akan menghargai jika seseorang bisa menjelaskannya dengan lebih baik). Pada setiap iterasi kita mengambil dua simpul yang tidak berdekatan dari grafik , menggabungkan dan dan mendapatkan grafik yang merupakan input kami yang lebih pendek ke oracle. Oracle menjawab apakah itu 3-warna atau tidak. Sekarang masalahnya adalah sebelum mengatur pada input oracle saya harus mewarnai vertex yang digabung dan menguji colorability dari , jika itu bukan perubahan warna 3-colorable, tetapi bagaimana menerapkannya dengan benar, saya perlu pengkodean yang tepat untuk itu. $x,y$ $G$ $x$ $y$ $G'$ $G'$ $G'$

reducibilitas diri

Pertama, kita harus memeriksa apakah grafik diberi 3-warna sama sekali, jadi aturlah pada input oracle, dan oracle akan menjawab jika itu 3 - berwarna, jika ya maka mulailah prosesnya. Dua simpul yang tidak bersebelahan dapat memiliki warna yang sama dalam grafik 3-warna. Proses reducibilitas diri kita harus berjalan dalam iterasi, saya pikir kita bisa mulai dari subgraf kecil dari grafik diberikan dan pada setiap iterasi tambahkan satu lagi simpul dari ke . Secara paralel, kita harus mempertahankan tugas simpul yang sudah berwarna. Sayangnya, saya masih belum mendapatkan ide sepenuhnya. Akan menghargai bantuan dan petunjuk. $G$ $G'$ $G$ $G$ $G'$

complexity-theory reductions com
sumber

hanya sebuah catatan: Saya berpikir bahwa dalam pengurangan sendiri Anda harus menggunakan versi "telanjang" dari masalah keputusan: input dari masalah keputusan adalah grafik dan bukan grafik dengan beberapa node berwarna. Jadi, Anda harus memodifikasi grafik asli untuk mensimulasikan pewarnaan paksa dari beberapa node (dan mencoba untuk membuat instance lebih pendek). Dalam SAT ini lebih mudah karena Anda hanya menetapkan nilai variabel dan menyederhanakan klausa.

Vor

Apa perbedaan antara reducibilitas diri sendiri dan redukibilitas diri sendiri ke bawah?

Yuval Filmus

@YuvalFilmus, set adalah self- reducible ke bawah jika ada Cook-reduksi untuk dirinya sendiri yang membuat kueri yang masing-masing lebih pendek dari input reduksi (pada input reduksi membuat kueri lalu )

S

$S$

S

$S$

x

$x$

q

$q$

| q | < | x |

$|q| < |x|$

com

Sedangkan satu set dapat direduksi sendiri jika ...?

Yuval Filmus

Masalah pencarian dari setiap relasi disebut self-reducible jika dapat direduksi menjadi masalah keputusan .

R

$R$

S_{R}

$S_R$

com

Jawaban:

Seperti yang disebutkan Vor dalam komentarnya, reduksi Anda tidak berfungsi, karena 3-colorability tidak menerima penetapan sebagian warna. Masalah akan lebih dalam, karena pengaturan warna simpul tunggal tidak membuat setiap kemajuan dalam menentukan apakah grafik adalah 3-yg berhasil: memang, grafik adalah 3-yg berhasil IFF ada 3-mewarnai di mana simpul adalah warna yang ditugaskan , untuk setiap Anda pilih. $v$ $c$ $v,c$

Berikut ini adalah petunjuk tentang cara menyelesaikan latihan Anda, bagian kedua. Dalam setiap 3-pewarnaan grafik pada lebih dari tiga simpul, ada dua simpul mendapatkan warna yang sama (mengapa?). Jika kita menggabungkan dan , grafik yang dihasilkan masih 3-warna (mengapa?). Coba gunakan ide ini untuk membuat algoritma pengurangan sendiri ke bawah untuk 3-warna. $G$ $x,y$ $x$ $y$

Sunting: Dan di sini ada petunjuk tentang bagaimana menyelesaikan latihan, bagian pertama. Pertimbangkan dua simpul yang tidak terhubung . Jika ada pewarnaan di mana mereka mendapatkan warna yang sama maka adalah 3-colorable (mengapa?), Dan pewarnaan dapat diekstraksi dari pewarnaan (bagaimana?). Kapan proses ini akan berhenti? $x,y$ $G_{xy}$ $G$ $G_{xy}$

Yuval Filmus
sumber

Poin tambahan jika Anda dapat menemukan pengurangan yang memanggil oracle kali.

O (1)

$O(1)$

Yuval Filmus

Terima kasih banyak atas petunjuk itu, bukan pewarna parsial, kita dapat menggunakan auxiliar graph dan memperpanjang sesuai untuk . Grafik dengan lebih dari tiga simpul memiliki dua simpul dengan warna yang sama, hanya karena oracle menjawab bahwa itu 3-warna (tetapi simpul lebih dari tiga), jadi harus ada simpul dengan warna yang sama. Tapi saya tidak mengerti mengapa grafik masih 3-warna ketika kita menggabungkan dua simpul dengan warna yang sama. Di sisi lain, mengapa kita perlu menambahkan tepi antara simpul yang sudah berwarna.

G^{'}

$G'$

G

$G$

G

$G$

x, y

$x, y$

com

Menurut jumlah panggilan. Secara umum, kami dapat menetapkan warna yang sama untuk semua simpul yang tidak bersebelahan, oleh karena itu dalam hal ini kami tidak harus meminta oracle pada setiap penugasan (di sisi lain, ada tiga warna, dan sangat penting untuk mengambil penugasan yang tepat. Tampaknya tugas yang benar pada , dapat menjadi salah pada ).

G^{'}

$G'$

G

$G$

com

Misalkan grafik memiliki 3-warna sehingga . Sekarang perhatikan grafik diperoleh dengan menggabungkan dan . Bisakah Anda menemukan 3 warna untuk ? Bagaimana dengan yang sebaliknya?

G

$G$

c

$c$

c (x) = c (y)

$c(x) = c(y)$

G_{x y}

$G_{xy}$

x

$x$

y

$y$

G_{x y}

$G_{xy}$

Yuval Filmus

Sekarang saya mengerti perbedaan antara reducibilitas diri dan redukibilitas diri ke bawah, saya perhatikan bahwa petunjuk saya hanya masuk akal untuk yang terakhir. Menambahkan petunjuk berbeda untuk yang pertama. Mungkin itu membantu.

Yuval Filmus

Mungkin seperti ini Kita dapat menambahkan dua vertex terhubung l1 dan l2. Pertama, kami menghubungkan mereka dengan vertex v *. Perhatikan bahwa perilaku ini berarti bahwa pada akhirnya, kita hanya mengunci beberapa warna pada titik termasuk v *.

Kemudian kami menjalankan versi keputusan dari 3-colorability, jika algoritma keputusan menerima, maka kami menambahkan simpul ini ke s_1. kita ulangi langkah ini dengan setiap simpul (hubungkan l1 dan l2 dengan simpul lain), kita akan menemukan bahwa pada akhirnya, semua simpul dengan warna yang sama (ditemukan dengan warna merah) ditemukan, dan simpul ini dengan warna merah dilambangkan dengan s_1.

Jika ada masalah, harap tunjukkan. 🤥

Selanjutnya, sama seperti apa yang kita lakukan di atas, tambahkan dua vertex yang terhubung (l3 l4), Pertama, kita hubungkan mereka dengan vertex apa pun kecuali yang ada di s_1, jalankan algoritma keputusan. Kemudian .....

YK X
sumber