Liczba wierzchołków obecnych we wszystkich maksymalnych dopasowaniach

Biorąc pod uwagę wykres , musimy znaleźć liczność największego zestawu wierzchołków, aby każdy z nich był obecny w każdym możliwym maksymalnym dopasowaniu.$G$

Czy istnieje rozwiązanie obok oczywistego usunięcia każdego wierzchołka i znalezienia maksymalnego dopasowania, aby zobaczyć, że zmniejsza się?

Myślę, że chcesz rozkładu Edmonda-Gallai na swoim wykresie, który można obliczyć w czasie (patrz te uwagi ).$O(n^3)$

Czy twój wykres jest dwustronny? Ponieważ, jeśli tak jest: załóżmy, że jedna strona dwuczęściowa jest pozostawiona, a druga właściwa. Znajdź maksymalne dopasowanie i ustaw wszystkie dopasowane krawędzie od lewej do prawej oraz wszystkie niedopasowane krawędzie od prawej do lewej. Następnie wierzchołek można pominąć w maksymalnym dopasowaniu tylko wtedy, gdy spełniony jest jeden z trzech następujących (wzajemnie wykluczających się) warunków:$v$

• $v$ jest już niedopasowane
• $v$ można osiągnąć z niedopasowanego wierzchołka po jego stronie dwuczęściowego w wynikowym digrafie
• $v$ może osiągnąć niedopasowany wierzchołek po swojej stronie dwuczęściowej w wynikowym wykreślniku.

Wykonując dwa wyszukiwania najpierw szerokości lub pierwszego głębokości, jeden w celu znalezienia części wykresu, do których można dotrzeć z niedopasowanych wierzchołków, i drugi w celu znalezienia części, które mogą osiągnąć niedopasowane wierzchołki, można znaleźć niezbędne wierzchołki w czasie liniowym, gdy tylko już mam pasujące.

Prawdopodobnie coś takiego będzie działało również w przypadku dwustronnej, wykorzystując naprzemienne wyszukiwanie ścieżki alternatywnej, ale szczegóły będą bardziej skomplikowane.