Найти максимальное соответствие, которое насыщает данный набор вершин

Question

в невзвешенном двустороннем графе $ g= (x + y, e) $ , мы хотели бы найти максимальное соответствие, но среди всех этих максимальных совпадений, Мы хотели бы найти тот, который насыщает заданное подмножество $ x_0 \ subselec x $ .

Необходимое условие существования такого совпадения заключается в том, что $ x_0 $ удовлетворяет условию брака зала, т. Е. Для каждого $ X '\ subsEtq x_0 $ , количество соседей $ x' $ - это как минимум $ | X '| $ . Если это условие удовлетворено, мы можем найти соответствующий $ m $ , который насыщает все вершины $ x_0 $ , но $ m $ не обязательно является максимальным совпадением в $ G $ .

Всегда возможно расширить $ m $ в максимальное соответствие? В качестве альтернативы, есть ли другой способ найти максимальное соответствие, которое насыщает $ x_0 $ , когда необходимое условие удовлетворено?

Answer 1

После некоторых исследований я обнаружил, что мой вопрос - это особый случай проблемы проблемы Приоритетное соответствие .В этом случае есть два приоритетных класса, $ x_0 $ и $ x_1:= v \ setminus x_0 $ ОтказЦель состоит в том, чтобы найти соответствие, которое максимизирует количество насыщенных вершин в $ x_0 $ , и при условии, что количество насыщенных вершин в математике $ x_1 $ .Существуют эффективные алгоритмы, которые решают эту проблему для любого количества приоритетных классов.Известно, что любое приоритетное сопоставление также является сопоставлением максимальной кардинальности.