Finden Sie eine maximale Übereinstimmung, die einen bestimmten Satz von Scheitelpunkten sättigt

Question

in einem ungewehrten vipartiten graph $ g= (x + y, e) $ , wir möchten ein maximales Matching finden, aber unter allen maximalen Übereinstimmungen, Wir möchten einen finden, der eine gegebene Subset $ X_0 \ Subseteq x $ sättigt.

Eine notwendige Bedingung für das Vorhandensein einer solchen Übereinstimmung ist, dass $ X_0 $ Hall-Ehe-Zustand erfüllt, dh für jeden $ X '\ Subseteq x_0 $ , die Anzahl der Nachbarn von $ x' $ ist mindestens $ | X '| $ . Wenn diese Bedingung erfüllt ist, können wir einen passenden $ M $ finden, der alle Scheitelpunkte von $ X_0 $ sättigt> , aber $ M $ ist nicht unbedingt ein maximales Anpassen in $ g $ .

ist es immer möglich, $ m $ in eine maximale Übereinstimmung zu erweitern? Alternativ gibt es eine andere Möglichkeit, um ein maximales Anpassen zu finden, das gesättigt ist $ X_0 $ Wenn die erforderliche Bedingung erfüllt ist?

Answer 1

Nach einiger Forschung habe ich herausgefunden, dass meine Frage ein besonderer Fall des Problems des Problems von Priority Matching .In diesem Fall gibt es zwei Prioritätsklassen, $ X_0 $ und $ x_1:= v \ setminus x_0 $ .Ziel ist es, ein Matching zu finden, das die Anzahl der gesättigten Scheitelpunkte in $ X_0 $ $ maximiert und daraus darf, die Anzahl gesättigter Scheitelpunkte in $ x_1 $ .Es gibt effiziente Algorithmen, die dieses Problem für jede Anzahl von Prioritätsklassen lösen.Es ist bekannt, dass jede Prioritätsanpassung auch ein passendes Maximum-Kardinalität ist.