Perkiraan pewarnaan grafik dengan batas atas yang dijanjikan pada set independen maksimum

Dalam pekerjaan saya masalah berikut muncul:

Apakah ada algoritma yang diketahui, yang mendekati jumlah kromatik grafik tanpa urutan 65 yang independen? (Jadi alpha (G) <= 64 diketahui dan | V | / 64 adalah lebih rendah sepele, | V | batas atas sepele. Tetapi apakah ada perkiraan yang lebih baik terbukti dalam kondisi khusus ini?)

Bagaimana jika kita rileks ke nomor kromatik fraksional? Dan untuk menjalankan "baik" kali dalam kasus rata-rata?

ds.algorithms graph-algorithms approximation-algorithms graph-colouring cyrix42
sumber

Saya pikir ini adalah pertanyaan yang bagus untuk situs ini; mari kita berharap bahwa seseorang memiliki jawaban yang bagus.

Jukka Suomela

@TysonWilliams: Saya pikir pertanyaannya sangat jelas. Lupakan komentar, baca kembali pertanyaannya. :)

Jukka Suomela

Lucunya, kondisi ini menjamin bahwa pendekatan trivial adalah pendekatan 64 ke optimal. Saya bertanya-tanya apakah hanya janji sejumlah kecil kemerdekaan dapat memberikan algoritma yang lebih baik.

Sasho Nikolov

Apakah masalah dimotivasi oleh aplikasi praktis? Jika demikian, kita harus fokus pada heuristik menarik yang akan dilakukan dengan baik - meningkatkan pendekatan sepele 64 tidak begitu menarik.

Chandra Chekuri

O (n^{64})

$O(n^{64})$

Jawaban:

Hitung pencocokan maksimum dalam komplemen grafik input. Setiap simpul yang tidak cocok harus dalam kelas warna yang berbeda dalam pewarnaan apa pun. Jadi: jika Anda mendapatkan setidaknya cn tepi yang cocok, maka pencocokan itu sendiri memberi Anda pewarnaan dengan batas atas (1-c) n, dan rasio perkiraan 64 (1-c). Jika Anda tidak mendapatkan setidaknya cn edge, maka Anda mendapatkan batas bawah warna (1 - 2c) n dan rasio pendekatan 1 / (1-2c). Memecahkan persamaan 64 (1-c) = 1 / (1-2c) menghasilkan rasio pendekatan yang sedikit lebih besar dari 32; lihat komentar Sasho Nikolov untuk nilai tepatnya.

David Eppstein
sumber

c = 3 / 16 (4 - \sqrt{2}) \approx 0.5

$c = 3/16 (4-\sqrt{2}) \approx 0.5$

\approx 32

$\approx 32$

k

$k$

α (G)

$\alpha(G)$

\frac{k}{2}

$\frac{k}{2}$

k

$k$

$H$ $H$

http://en.wikipedia.org/wiki/Colouring_number#Algorithms

Andrew D. King
sumber

Koreksi kecil: tidak benar bahwa jumlah pewarnaan sama dengan jumlah warna paling sedikit dalam pewarnaan serakah. Jika Anda memesan simpul sesuai dengan warna mereka dalam pewarnaan yang optimal (dengan properti tambahan bahwa kelas warna pertama adalah maksimal, dan yang kedua adalah maksimal dalam grafik yang tersisa dll) maka algoritma serakah akan menemukan pewarnaan optimal yang sama.

David Eppstein