二部グラフの完璧なマッチングの分割

Question

「結婚の問題」では、N個の男の子とN個の女の子とNxNの2進数列があり、どのペアリングが適しているかを示しています。 （つまり、2つのグラフで完全な一致を見つけたいと思っています）。

ホールの定理によれば、少年ノードのすべての集合が少なくとも少数の少女ノードに集合的に隣接する場合、完全な一致を見つけることができます。これらのマッチングを完全に見つける高速増強パスアルゴリズムがあります。

に完全に隣接する少年ノードのコレクションを正確には個の少女ノード（つまり、私たちはホールの基準で等しい）を見つけるための効率的な方法を探しています。これらの少年は、これらの少女と、他の少女との残りの少女とペアにしなければならないので、すべてがこのパーティショニングを尊重します。

私のグラフ理論は少し錆びていますが、確かに2^N個のサブセットをすべて列挙し、それぞれの隣人を数えるよりも良い方法がなければなりませんか？

Answer 1

私があなたが望むものを理解していれば、悲しいかな、これを多項式時間で行うというスマートな方法はありません。一般的なグラフでそのようなパーティションを見つけることは、NP完全な問題です。

Answer 2

これは多項式時間で可能です。有向グラフの最大フロー問題として、バイパータイトのマッチング問題をモデル化します。次に、最小カットを列挙するためのアルゴリズムを使用します。 Googleで「最小カットを列挙する」、またはVazirani & YannakakisまたはYeh & Wangによる論文を検索してください。