Algoritme yang efisien untuk pewarnaan hypergraphs yang mendekati optimal

Masalah pewarnaan grafik sudah cukup sulit bagi kebanyakan orang . Meski begitu, saya harus sulit dan menanyakan masalah tentang pewarnaan hypergraph.

Pertanyaan.

Algoritme efisien apa yang ada untuk menemukan pewarnaan tepi yang kurang lebih optimal untuk hypergraphs k-uniform?

Detail ---

• Hypergraph k-uniform adalah di mana setiap sisi mengandung simpul k yang tepat; kasus biasa dari grafik sederhana adalah k = 2. Lebih tepatnya, saya tertarik pada hypergraphs berlabel k-uniform, di mana dua sisi sebenarnya memiliki set vertex yang sama; tapi saya akan puas dengan sesuatu pada k-reguler hypergraphs dengan ujung-ujungnya berpotongan tidak lebih dari k vert 1 simpul.

• Pewarnaan tepi dari hypergraphs adalah di mana ujung-ujungnya dengan warna yang sama tidak berpotongan, seperti halnya dengan grafik. Indeks kromatik χ '(H) adalah jumlah warna yang dibutuhkan, seperti biasa.

• Saya ingin hasil pada algoritma waktu polinomial deterministik atau acak.

• Saya mencari faktor pendekatan / aditif-gap yang paling dikenal antara apa yang dapat ditemukan secara efisien, dan indeks kromatik aktual χ '(H) --- atau dalam hal ini, hasil terbaik yang dapat dicapai secara efisien dalam hal parameter seperti derajat vertex maksimum Δ (H), ukuran hypergraph, dll.

Sunting: diminta oleh pernyataan Suresh tentang dual hypergraph di bawah ini, saya harus mencatat bahwa masalah ini setara dengan masalah menemukan pewarnaan simpul yang kuat dari hypergraph k-reguler : yaitu, di mana setiap simpul milik k tepi yang berbeda [tetapi ujungnya sekarang dapat berisi jumlah simpul yang berbeda], dan kami ingin pewarnaan simpul sehingga setiap simpul yang berdekatan memiliki warna yang berbeda. Reformulasi ini juga tampaknya tidak memiliki solusi yang jelas.

Catatan

Dalam kasus grafik, Teorema Vizing tidak hanya menjamin bahwa angka kromatik tepi untuk grafik G adalah Δ (G) atau Δ (G) +1, bukti standarnya juga memberikan algoritma yang efisien untuk menemukan Δ (G) ) + 1-tepi-pewarnaan. Hasil ini akan cukup baik bagi saya jika saya tertarik pada kasus k = 2; Namun, saya secara khusus tertarik pada k> 2 sewenang-wenang.

Tampaknya tidak ada hasil yang diketahui tentang batas pada pewarnaan tepi hypergraph, kecuali jika Anda menambahkan batasan seperti setiap tepi berpotongan di paling banyak simpul. Tapi aku tidak butuh batasan pada χ '(H) itu sendiri; hanya sebuah algoritma yang akan menemukan pewarnaan tepi yang "cukup baik". [Saya juga tidak ingin menempatkan batasan pada hypergraphs saya, kecuali karena k-uniform, dan mungkin terikat pada derajat verteks maksimum, misalnya Δ (H) ≤ f (k) untuk beberapa f ∈ ω (1) .]

[ Adendum. Saya sekarang telah mengajukan pertanyaan terkait pada MathOverlow tentang batasan pada nomor berwarna, konstruktif atau lainnya.]

Jawaban di bawah ini mematahkan kondisi Anda bahwa Anda tidak ingin pembatasan serius diberikan pada hypergraph Anda, tetapi mungkin menarik jika hanya sebagai pekerjaan terkait.

$r$$r$

Ada beberapa karya terbaru tentang masalah "pewarnaan warna-warni" untuk ruang jangkauan geometris, sebagian dimotivasi oleh masalah dalam jaringan sensor. Pertanyaan standar yang diajukan adalah:

$k$$S$$c_S(k)$$c_S(k)$$r$$S$$\min(|r|, k)$

$c_S(\Delta)$$\Delta$

$c_\tilde{S}(k)$$\tilde{S}$

$S$$\Re^2$$c_S(k) \le 3k-2$

Referensi yang baik untuk badan kerja ini adalah makalah DCG oleh Aloupsis et al , dan referensi di dalamnya.