特定の頂点セットを飽和させる最大マッチングを見つける

Question

浮いていないバイパイトグラフ $ g=（x + y、e）$ 、最大マッチングを見つけたいですが、それらすべての最大マッチングの中で、特定のサブセットを飽和させるものを見つけたいと思います。 $ x_0 \ subseteq x $ 。

そのようなマッチングの存在に必要な条件は、 $ x_0 $ がホールの結婚条件を満たす、つまり $ x '\ subseteq x_0 $ 、 $ x' $ の隣人数は少なくとも $です。 | X '| $ 。 この条件が満たされている場合は、 $ x_0 $ のすべての頂点を飽和させるマッチング $ m $ を見つけることができます。しかし、 $ m $ は必ずしも $ g $ の最大マッチングではありません。

$ m $ を最大マッチングに拡張することは常に可能ですか？あるいは、 $ x_0 $ を満足するときに最大マッチングを見つけるのは異なる方法がありますか？

Answer 1

研究の後、私の質問は優先順位の一致<の問題の特別な場合であることがわかりました。/ a>。この場合、 $ x_0 $ 、および $ x_1：= v \ setminus x_0 $ の2つの優先クラスがあります。。目標は、 $ x_0 $ 内の飽和頂点の数を最大にするマッチングを見つけること、 $ x_1 $ 。任意の数の優先クラスについてこの問題を解決する効率的なアルゴリズムがあります。任意の優先順位の一致も最大濃度マッチングであることが知られている。