Czy istnieje sposób na obliczenie wielkości maksymalnego dopasowania na nieważonym grafie dwustronnym bardziej efektywnie (np. Szybciej) niż obliczenie maksymalnego dopasowania?
Jest to dalekie ujęcie, ale często interesującym problemem jest unikanie takich niepotrzebnych obliczeń.
Motywacja
Problem, który próbuję rozwiązać, to match-2, w którym oba zestawy mają różne rozmiary. Muszę ustalić, czy istnieje dopasowanie, które obejmuje wszystkie wierzchołki z mniejszego zestawu. Znając rozmiar maksymalnego dopasowania pozwoliłbym sprawdzić, czy jest on równy lub mniejszy niż rozmiar mniejszego zestawu (jeśli taka rzecz jest możliwa, to za każdym razem, gdy wynikiem jest „tak, istnieje dopasowanie obejmujące mały zestaw „skutecznie wiedziałbyś, jaki jest jego rozmiar, ale tylko w takim przypadku), ale nie jest to absolutnie konieczne: jeśli istnieje sposób na obliczenie odpowiedzi bez obliczenia rozmiaru, jest to dla mnie dobre.