Trova una corrispondenza massima che satura un determinato set di vertici

Question

in un grafico bipartite non lavorato $ g= (x + y, e) $ , vorremmo trovare una corrispondenza massima, ma tra tutte quelle corrispondenze massime, Vorremmo trovarne uno che satura un dato sottoinsieme $ x_0 \ SOTETETQ x $ .

Una condizione necessaria per l'esistenza di tale corrispondenza è quella $ x_0 $ soddisfa le condizioni di matrimonio della sala, cioè per ogni $ X '\ SOCSETETQ X_0 $ , il numero di vicini di $ x' $ è almeno $ | X '| $ . Se questa condizione è soddisfatta, possiamo trovare una corrispondenza $ m $ che satura tutti i vertici di $ x_0 $ , ma $ m $ non è necessariamente una corrispondenza massima in $ G $ .

È sempre possibile estendere $ m $ in una corrispondenza massima? In alternativa, c'è un modo diverso per trovare una corrispondenza massima che satura $ x_0 $ quando la condizione necessaria è soddisfatta?

Answer 1

Dopo alcune ricerche, ho scoperto che la mia domanda è un caso speciale del problema di corrispondenza prioritaria .In questo caso ci sono due classi di priorità, $ x_0 $ e $ x_1:= v \ setminus x_0 $ .L'obiettivo è trovare una corrispondenza che massimizza il numero di vertici saturi in $ x_0 $ e soggetto a ciò, il numero di vertici saturi in $ x_1 $ .Ci sono algoritmi efficienti che risolvono questo problema per qualsiasi numero di classi prioritarie.È noto che qualsiasi corrispondenza prioritaria è anche una corrispondenza massima della cardinalità.