Encontre uma correspondência máxima que sature um determinado conjunto de vértices

Question

em um gráfico bipartido indeciso $ g= (x + y, e) $ , gostaríamos de encontrar uma correspondência máxima, mas entre todas as correspondências máximas, Gostaríamos de encontrar um que sature um dado subconjunto $ x_0 \ subseteq x $ .

Uma condição necessária para a existência de tal correspondência é que $ x_0 $ satisfaz a condição de casamento do salão, ou seja, para cada $ X '\ subseteq x_0 $ , o número de vizinhos de $ x' $ é pelo menos $ | X '| $ . Se esta condição estiver satisfeita, podemos encontrar uma correspondência $ m $ que sature todos os vértices de $ x_0 $ , mas $ m $ não é necessariamente uma correspondência máxima na $ g $ .

É sempre possível estender $ m $ em uma correspondência máxima? Alternativamente, há uma maneira diferente de encontrar uma correspondência máxima que saturado $ x_0 $ quando a condição necessária é satisfeita?

Answer 1

Após alguma pesquisa, descobri que minha pergunta é um caso especial do problema de Prioridade correspondente .Nesse caso, há duas classes prioritárias, $ x_0 $ e $ x_1:= v \ setminus x_0 $ .O objetivo é encontrar uma correspondência que maximiza o número de vértices saturados na $ x_0 $ e sujeito a isso, o número de vértices saturados na matemática $ x_1 $ .Existem algoritmos eficientes que resolvem esse problema para qualquer número de classes prioritárias.Sabe-se que qualquer correspondência de prioridade também é uma correspondência máxima de cardinalidade.