找到最大匹配，使一组给定的顶点饱和

Question

在一个未加权的二分钟图 $ g=（x + y，e）$ ，我们想找到最大匹配，但在所有这些最大匹配中，我们想找到一个饱和子集 $ x_0 \ subseteq x $

的子集。

存在这样的匹配的必要条件是 $ x_0 $ 满足Hall的婚姻状况，即，对于每个 $ x'\ subseteq 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 $ 。有效的算法可以解决任意数量的优先级的问题。众所周知，任何优先级匹配也是最大基数匹配。