Apa kerumitan masalah pewarnaan tepi ini?

17

Baru-baru ini, saya menemukan varian pewarnaan tepi berikut.

Diberikan grafik tidak terarah yang terhubung, temukan pewarnaan tepi yang menggunakan jumlah warna maksimum dan juga memenuhi kendala bahwa, untuk setiap simpul , insiden tepi untuk paling banyak menggunakan dua warna.vv

Dugaan pertama saya adalah bahwa masalahnya adalah NP-hard. Bukti NP-hard klasik untuk masalah pewarnaan graf sebagian besar oleh reduksi dari 3SAT. Tetapi menurut pendapat saya, bukti-bukti ini tidak berguna untuk masalah ini karena insiden edge pada vertex dapat diwarnai dengan warna yang sama, jadi kita tidak dapat membuat komponen logika dalam grafik.

Mungkinkah masalah ini NP-hard? Jika ya, apa buktinya? Jika kita tidak dapat membuktikan bukti, apakah ada metode untuk menentukan kompleksitas masalah ini?

Terima kasih!

cc.complexity-theory np-hardness complexity-classes graph-colouring RIC_Eien
sumber
Mungkin Pewarnaan Hypergraph Berwarna Campuran atau Berwarna mungkin merupakan awal? Misalnya, dx.doi.org/10.1016/j.disc.2008.04.019
András Salamon
Tampaknya masalah Anda ada di P, dalam dua langkah: (1) masalah Anda setara dengan menemukan subset tepi ukuran maksimum sehingga setiap simpul memiliki paling banyak dua, dan (2) masalah yang terakhir tampaknya ada di P oleh, katakanlah, reduksi ke pencocokan. Mengenai (1), perhatikan bahwa solusi apa pun untuk masalah Anda dengan k colors memberikan derajat-2 subgraph ukuran k (hanya mempertahankan satu sisi dari setiap warna), dan sebaliknya setiap derajat-2 subgraph ukuran k memberikan solusi dengan k colors (cukup warnai setiap tepi dalam subgrafanya dengan warnanya sendiri, warnai sisa tepinya dengan salah satu dari warnanya). Apa yang saya lewatkan?
Neal Young
Saya menyesal ada beberapa kesalahan dalam jawaban Anda. Pada awalnya, masalah "menemukan subset ukuran-maksimum tepi sehingga setiap simpul memiliki paling banyak dua", adalah NP-hard, reduksi menjadi 3SAT (Saya tidak benar-benar tahu bagaimana bisa ada pengurangan untuk mencocokkan). Terlebih lagi, "setiap derajat-2 ukuran huruf k" tidak memberikan "solusi dengan warna k", misalnya, Grafik Lengkap. Terima kasih semua.
RIC_Eien
Ya kau benar. Tentang (2), langkah "warna sisa tepi dengan salah satu warna" dapat memberikan beberapa ujung simpul dari tiga warna. Secara terpisah, Marek Chrobak menyarankan algoritma berikut kepada saya. Saya pikir itu memberikan perkiraan-3: (i) menemukan pencocokan maksimum M; (ii) warna setiap tepi dalam M warna uniknya sendiri; (iii) warna sisa tepi putih.
Neal Young
@RIC_Eien: Dengan risiko dipermalukan lebih lanjut .. Apakah Anda yakin "masalah 'menemukan subset tepi ukuran maksimum sehingga setiap simpul paling banyak memiliki dua', apakah NP-hard"? Diberikan G = (V, E), buat bipartit G2 = (U, W, E2), di mana untuk setiap simpul v di V ada v 'di U dan v' 'di W, dan E2 = {(u', w ''): (u, w) dalam E}. Kemudian pencocokan dalam G2 sesuai dengan set derajat-2 tepi dalam G, dan korespondensi mempertahankan ukuran? (Karena setiap k-siklus C dalam G bersesuaian dalam G2 dengan siklus 2k (jika k aneh) atau dua siklus-k (jika k datar).) Jadi, pencocokan maks dalam G2 menyelesaikannya. Apa yang saya lewatkan saat ini?
Neal Young

Jawaban:

15

q

Aspek kompleksitas parameter dari masalah ini dibahas dalam makalah ini .

vb le
sumber
Saya telah memikirkan sementara tentang masalah yang menyenangkan ini ... Bisakah Anda jelaskan pengurangannya? Saya tidak punya akses ke koran. Terima kasih!
user13667
5
@ user13667 Anda dapat meminta penulis mengirimi Anda salinan makalah mereka. Saya pikir mereka akan senang melakukannya.
vb le
5
Pertanyaan terkait untuk menemukan pewarnaan yang memaksimalkan jumlah warna sambil meminimalkan ukuran kelompok warna terbesar juga telah dipelajari. Sebagai contoh, Tesis Master ini memiliki beberapa hasil terperinci.
Neeldhara