Apakah ada cara untuk menghitung ukuran pencocokan maksimum dalam grafik bipartit tak tertimbang lebih efisien (mis. Lebih cepat) daripada menghitung pencocokan maksimum?
Ini adalah pukulan panjang tetapi seringkali merupakan masalah yang menarik untuk menghindari perhitungan yang dibuang seperti ini.
Motivasi
Masalah yang saya coba selesaikan adalah match-2 di mana kedua set memiliki ukuran yang berbeda. Saya perlu menentukan apakah ada yang cocok yang mencakup semua simpul dari set yang lebih kecil. Mengetahui ukuran pencocokan maksimum akan membiarkan saya memeriksa apakah itu sama dengan atau lebih kecil dari ukuran himpunan yang lebih kecil (jika hal seperti itu memungkinkan maka kapan pun hasilnya adalah "ya, ada kecocokan yang mencakup himpunan kecil "Anda akan secara efektif mengetahui ukurannya tetapi hanya dalam kasus itu), tetapi itu tidak sepenuhnya diperlukan: jika ada cara untuk menghitung jawabannya tanpa menghitung ukurannya, itu baik untuk saya.