Jumlah minimum warna mencegah subtriangle berwarna seragam yang sama sisi

13

Dalam Bundeswettberweb Infomatik 2010/2011, ada masalah yang menarik:

Untuk fix , temukan minimal k dan peta φ : { ( i , j ) | i j n } { 1 , ... , k } , sedemikian sehingga tidak ada tiga ( i , j ) , ( i + l , j ) , ( i + l , j + l ) dengan φ ( inkφ:{(i,j)|ijn}{1,,k}(i,j),(i+l,j),(i+l,j+l) .φ(i,j)=φ(i+l,j)=φ(i+l,j+l)

Yaitu kami sedang mencari jumlah minimal warna untuk sebuah segitiga, sehingga tidak ada subtriangle sama sisi berwarna seragam (gambar berikut menunjukkan pewarnaan yang tidak valid karena simpul yang disorot membentuk subtriangle sama sisi berwarna sama):

                              Contoh

Bahkan mereka meminta cukup kecil untuk n = 1000 dan dalam solusi (ditulis dalam bahasa Jerman) mereka mencatat bahwa pendekatan rakus menghasilkan pewarnaan dengan 27 warna untuk n = 1000kn=100027n=1000 , yang dapat dikurangi menjadi dengan mengacak warna hingga solusi yang valid ditemukan.15

Saya tertarik pada solusi yang tepat (untuk lebih kecil ). Solusinya mengatakan bahwa backtracking menghasilkan 2 warna yang cukup untuk n { 2 , 3 , 4 } dann2n{2,3,4} cukup untuk 5 n 17 , di mana backtracking sudah sangat lambat untuk n = 17 .35n17n=17

Pertama saya mencoba menggunakan formulasi ILP dan Gurobi untuk mendapatkan beberapa hasil untuk , tapi itu terlalu lambat (sudah untuk n = 17 ). Kemudian saya menggunakan pemecah SAT , karena saya perhatikan bahwa ada formulasi lurus ke depan sebagai instance-SAT.n>17n=17

Dengan pendekatan itu saya dapat menghasilkan solusi dengan warna untuk n = 18 dalam 10 menit:3n=1810

                              Solusi dengan 3 warna untuk 18 node

Tetapi untuk memutuskan apakah warna sudah cukup untuk n = 19 sudah terlalu lambat. Apakah ada beberapa pendekatan berbeda yang memberikan solusi tepat untuk n 3n=19 ? Tentu saja kita tidak dapat mengharapkan algoritma polinomial.n19

Daftar
sumber
pertanyaan yang menarik. mengapa Anda mengatakan kami tidak dapat mengharapkan algoritma waktu polinomial?
Sasho Nikolov
@SashoNikolov itu hanya asumsi karena ini tampaknya lebih sulit daripada menemukan pewarnaan simpul yang valid (lebih sulit dalam hal lebih banyak kendala), dan pewarnaan simpul sudah merupakan masalah yang sangat sulit.
Listing

Jawaban:

10

Hanya komentar yang diperluas:

Anda dapat melihat pendekatan yang digunakan oleh Steinbach dan Posthoff untuk menemukan 4-pewarnaan kisi 18x18 (dan 12x21) tanpa persegi panjang monokromatik :

Bernd Steinbach dan Christian Posthoff, Solusi dari Grid Terbuka Empat-Warna Terakhir Yang Terbuka Tanpa Warna Masalah Kompleks Berharga Banyak yang Sangat Kompleks . Dalam Prosiding Simposium Internasional ke-43 IEEE 2013 tentang Multiple-Valued Logic (ISMVL '13)

Sebagaimana dibuktikan oleh Gasarch et al. diberikan color parsial yang sewenang-wenang ncn×m

Hanya catatan tambahan: Saya menghabiskan berminggu-minggu siklus CPU pada masalah 4 warna pewarnaan empat-persegi monokromatik tapi saya mulai dari hasil parsial yang salah (analisis sebelumnya yang salah yang membatasi jumlah kemungkinan sub-konfigurasi 1 warna) dan saya menggunakan itu STP kendala pemecah ; Anda dapat mencapai peningkatan besar jika Anda menambahkan kendala yang memecah simetri (mis. pemesanan pada pewarnaan sisi segitiga) dan mencoba membuat analisis konfigurasi yang mungkin hanya menggunakan 1-warna.

EDIT: ini adalah hasil dari program STP untuk n = 19 (~ 1 mnt)

masukkan deskripsi gambar di sini

Marzio De Biasi
sumber
n=19
4

n22n=22n=23n=23n=23 ).

n=19n=23

n=22

tri22-sol

Terima kasih banyak kepada Marzio karena menghasilkan gambar, dan telah memberi tahu saya tentang masalahnya! :-)

Juho
sumber