Apakah ada pengurangan langsung / alami untuk menghitung pencocokan sempurna non-bipartit menggunakan permanen?

Menghitung jumlah kecocokan sempurna dalam grafik bipartit segera dapat direduksi menjadi komputasi permanen. Karena menemukan pencocokan sempurna dalam grafik non-bipartit adalah dalam NP, terdapat beberapa pengurangan dari grafik non-bipartit menjadi permanen, tetapi mungkin melibatkan blowup polinomial yang buruk dengan menggunakan pengurangan Cook ke SAT dan kemudian teorema Valiant untuk mereduksi ke permanen.

Pengurangan yang efisien dan alami dari grafik non-bipartit ke matriks mana akan berguna untuk implementasi aktual untuk menghitung pencocokan sempurna dengan menggunakan ada, perpustakaan sangat dioptimalkan yang menghitung permanen. $f$ $G$ $A = f(G)$ $\operatorname{perm}(A) = \Phi(G)$

Diperbarui: Saya menambahkan karunia untuk jawaban termasuk fungsi yang dapat dihitung secara efisien untuk mengambil grafik arbitrer ke grafik bipartit dengan jumlah pencocokan sempurna yang sama dan tidak lebih dari simpul. $G$ $H$ $O(n^2)$

graph-theory counting-complexity reductions permanent Derrick Stolee
sumber

Judul saat ini terdengar seperti pertanyaan pekerjaan rumah, tetapi pertanyaan sebenarnya jauh lebih menarik dari itu. Saya bahkan hampir tidak membuka pertanyaan b / c. Saya pikir itu adalah pekerjaan rumah dan akan segera ditutup, sampai saya melihat itu sudah memiliki 9 upvotes dan penasaran ... Mungkin mengubah judul menjadi sesuatu yang lebih sesuai: " Apakah ada pengurangan langsung / alami untuk menghitung pencocokan sempurna non-bipartit menggunakan permanen? "

Joshua Grochow

Ide bagus. Aku bahkan tidak memikirkan itu. Terima kasih.

Derrick Stolee

Nitpicking: “Karena menemukan pasangan yang cocok di grafik non-bipartit ada di NP” → → “Karena menghitung pasangan yang cocok di grafik non-bipartit ada di #P”

Tsuyoshi Ito

Nitpicking Anda benar, dan saya mempertimbangkan untuk menulisnya, tetapi cara saya menulisnya mengisyaratkan bahwa pengurangan tersebut berlaku untuk pengurangan Cook THEN Valiant. Saya mencari pengurangan langsung dan efisien.

Derrick Stolee

Ada reduksi yang menghindari Cook: pertama-tama tuliskan formula VNP untuk pencocokan sempurna (saya bisa memikirkan yang sangat mirip dengan yang untuk permanen dan yang memiliki ukuran ). Kemudian, dengan universalitas permanen, ini dapat ditulis sebagai permanen dari matriks ukuran . Ini menggunakan fakta bahwa rumus ukuran dapat ditulis sebagai permanen dari matriks ukuran . Lebih langsung daripada melalui Cook, tetapi masih tidak langsung / alami seperti cara perm menghitung pencocokan sempurna dalam grafik bipartit.

\leq 4 n^{4}

$\leq 4n^4$

4 n^{4} + 1

$4n^4 +1$

S

$S$

S + 1

$S+1$

Joshua Grochow

Jawaban:

Saya akan mengatakan bahwa pengurangan "sederhana" ke pencocokan bipartit sangat tidak mungkin. Pertama, itu akan memberikan algoritma untuk menemukan pencocokan sempurna dalam grafik umum menggunakan metode Hungaria. Oleh karena itu, reduksi harus mengandung semua kompleksitas algoritma bunga Edmond. Kedua, ini akan memberikan LP kompak untuk polytope yang cocok sempurna dan karenanya pengurangan tidak harus simetris (yang dikesampingkan oleh hasil Yannakakis) dan pada dasarnya sangat rumit.

Mohit Singh
sumber

Ini semua adalah alasan bagus mengapa ini tidak mungkin ada. Seharusnya saya meminta bantahan dalam pertanyaan itu. Saya mungkin akan memberikan hadiah untuk jawaban ini, kecuali seseorang membuktikan Anda salah.

Derrick Stolee

Meskipun itu bukan jawaban yang saya inginkan, saya menemukan ini jawaban yang sangat memuaskan.

Derrick Stolee

@MohitSingh Bisakah Anda jelaskan 'tidak adanya metode hungaria untuk grafik non-bipartit', 'apa yang mengandung semua kompleksitas algoritma blossom' dan mengapa ini memberikan 'LP ringkas untuk pencocokan sempurna dan jadi tidak boleh simetris' ?

T ....

Ini jelas merupakan komentar dan bukan jawaban, tetapi saya belum memiliki poin reputasi di sini, maaf tentang hal itu.

Untuk grafik tanpa jembatan kubik non-bipartit, ada banyak pencocokan sempurna secara eksponensial, seperti dugaan Lovàsz dan Plummer pada tahun 70-an. Makalah ini dalam persiapan. Ini mungkin sangat relevan dengan pertanyaan Anda, atau mungkin tidak sama sekali.

Andrew D. King
sumber