Menghitung dan menemukan semua kecocokan sempurna / maksimum dalam grafik umum

Baru-baru ini saya telah berurusan dengan masalah yang mengarahkan saya ke pertanyaan-pertanyaan berikut:

• Apakah ada algoritma yang baik untuk menghitung semua pencocokan maksimum / sempurna dalam grafik umum?
• Apakah ada algoritma yang baik untuk menemukan semua pencocokan maksimum / sempurna dalam grafik umum?
• Apakah kedua masalah ini setara dalam kompleksitasnya?

Saya menemukan referensi berikut:

• Algoritma untuk Menghitung Semua Pencocokan Maksimum dan Maksimal yang Sempurna Dalam Grafik Bipartit - Menyarankan algoritma untuk menghitung semua pencocokan maksimum dalam grafik bipartit.
• Menemukan Semua Kecocokan Sempurna dalam Grafik Bipartit - Menyarankan algoritma untuk menemukan semua kecocokan sempurna dalam grafik bipartit

Kompleksitas kedua algoritma bergantung pada jumlah pencocokan sempurna dalam grafik (artinya waktu berjalan eksponensial dalam kasus terburuk).

Terlebih lagi, kedua artikel tersebut berhubungan dengan grafik bipartit, saya tidak dapat menemukan artikel serupa yang berurusan dengan masalah yang sama dalam grafik umum.

Saya menghargai informasi dan referensi tentang masalah di atas.

Menghitung jumlah kecocokan sempurna dalam grafik bipartit sama dengan menghitung permanen matriks 0-1, yang merupakan -complete. Oleh karena itu ada pengurangan dari semua masalah penghitungan lain yang Anda sebutkan (yang semuanya ada di ) untuk masalah ini. Anda dapat menghitung jumlah pencocokan sempurna dalam grafik bipartit planar , dan Anda dapat memperkirakan jumlah pencocokan sempurna dalam grafik bipartit umum. Lihat misalnya survei ini . Perkiraan jumlah pencocokan sempurna dalam grafik umum tampaknya lebih sulit, lihat misalnya makalah ini atau makalah itu$\# P$$\# P$. Kedua makalah menyebutkan bahwa algoritme mereka tampaknya berkinerja baik pada grafik acak, tetapi tidak selalu sebaik itu dalam kasus terburuk.

Masalah penghitungan dan penghitungan kecocokan dalam grafik berbeda-beda, jadi sulit untuk mengatakan apakah mereka "setara". Namun, perlu diketahui bahwa jika Anda dapat menghitung pencocokan maka Anda dapat menghitungnya. Ini menunjukkan bahwa, dalam beberapa hal, menghitung lebih sulit daripada menghitung. Untuk kasus pencocokan sempurna dalam grafik bipartit, tampaknya ada perbedaan, karena Anda dapat memperkirakan jumlah pencocokan sempurna, tetapi menghitungnya persis -hard.$\# P$