Menemukan pencocokan yang kontraksinya meminimalkan jumlah busur dalam grafik

10

Diberikan grafik campuran G=(V,E,A) dengan tepi E dan busur A , cari kecocokan dalam E yang meminimalkan jumlah busur dalam G/M , di mana G/M diperoleh dari G dengan mengontrak simpul yang cocok dan menghapus busur paralel.

Apakah (versi keputusan) masalah ini NP-complete? Apakah sudah dipelajari dalam literatur?

Marcus Ritt
sumber
2
Apakah penting apakah Anda memiliki busur atau tidak?
Suresh Venkat
@ Suresh: Sebenarnya tidak, A bisa tidak diarahkan. Intinya adalah bahwa satu set tepi menentukan titik mana yang dapat dicocokkan dan pencocokan meminimalkan jumlah tepi setelah kontraksi pada set sisi lainnya.
Marcus Ritt
2
ah baiklah jadi benar-benar pertanyaan bisa disederhanakan untuk hanya memiliki grafik G tidak terarah, tanpa dua set E dan A.
Suresh Venkat
Saya tidak yakin. Ketika ujung-ujungnya tidak diarahkan, kita bisa mengurangi masalah ke case yang diarahkan dengan mengganti setiap edge dengan dua yang diarahkan; tetapi dalam kasus yang diarahkan, jumlah busur setelah kontraksi tergantung pada arahnya, karena dua busur antara simpul yang sama tidak harus paralel. Jadi dengan mengabaikan arah busur, pencocokan optimal mungkin berbeda.
Marcus Ritt

Jawaban:

8

Saya tidak tahu apakah maksud Anda adalah untuk memungkinkan tepi yang tidak diarahkan pada E dan busur di A menjadi paralel atau tidak, tetapi pada akhirnya tidak masalah. Dalam jawaban ini, kami berasumsi bahwa Anda tidak mengizinkan tepi dan busur paralel.

Pertimbangkan kasus khusus di mana untuk setiap busur di A , A juga berisi busur di arah yang berlawanan. Dalam hal ini, kita dapat mengabaikan orientasi busur dan menganggapnya tidak terarah. Kami menyebutnya tepi di E tepi hitam dan tepi di A merah tepi .

x1,,xnv1,,vn,x1,,xn,x¯1,,x¯n(vi,xi)(vi,x¯i)5(n2)mvivjxixj(l,l)=(xi,xj),(xi,x¯j),(x¯i,xj),(x¯i,x¯j)ldan dengan tepi merah jika dan hanya jika klausa tidak muncul di φ .l(l¯l¯)

Jelas bahwa kita hanya perlu mempertimbangkan kecocokan maksimal pada tepi hitam untuk meminimalkan jumlah tepi merah setelah kontraksi. Juga jelas bahwa setiap pencocokan M maksimum di tepi hitam terdiri dari n tepi yang menghubungkan ke untuk i = 1, ..., n . Identifikasikan M yang cocok ini dengan penugasan kebenaran . Sangat mudah untuk memverifikasi bahwa setelah berkontraksi M dan menghilangkan tepi paralel, grafik memiliki tepat tepi merah, di mana kvili{xi,x¯i}{l1,,ln}4(n2)kadalah jumlah klausa yang puas dengan penugasan kebenaran ini. Oleh karena itu, meminimalkan jumlah tepi merah setelah mengontrak pencocokan di tepi hitam sama dengan memaksimalkan jumlah klausa yang puas.

Tsuyoshi Ito
sumber
Terima kasih! (Typo: klausa seharusnya .)(l¯l¯)
Marcus Ritt
@ Marccus: Terima kasih kembali, dan terima kasih telah menunjukkan kesalahan ketik.
Tsuyoshi Ito