Encuentre una coincidencia máxima que satura un conjunto dado de vértices

Question

En un gráfico bipartito no ponderado $ g= (x + y, e) $ , nos gustaría encontrar una coincidencia máxima, pero entre todas esas coincidencias máximas, Nos gustaría encontrar uno que satule un subconjunto dado $ x_0 \ subestesteq x $ .

Una condición necesaria para la existencia de tal coincidencia es que $ x_0 $ satisface la condición de matrimonio de la sala, es decir, para cada $ X '\ subestex x_0 $ , el número de vecinos de $ x' $ es al menos $ | X '| $ . Si se cumple esta condición, podemos encontrar un $ m $ que satura todos los vértices de $ x_0 $ , pero $ m $ no es necesariamente una coincidencia máxima en $ g $ .

¿Siempre es posible extender $ m $ en una coincidencia máxima? Alternativamente, ¿existe una forma diferente de encontrar una coincidencia máxima que sature $ x_0 $ cuando se cumple la condición necesaria?

Answer 1

Después de una investigación, descubrí que mi pregunta es un caso especial del problema de coincidencia de prioridad .En este caso, hay dos clases prioritarias, $ x_0 $ y $ x_1:= v \ setminus x_0 $ .El objetivo es encontrar una coincidencia que maximice el número de vértices saturados en $ x_0 $ y sujeto a eso, el número de vértices saturados en $ x_1 $ .Hay algoritmos eficientes que resuelven este problema para cualquier número de clases prioritarias.Se sabe que cualquier coincidencia prioritaria es también una coincidencia de cardinalidad máxima.