切断された2部グラフの頂点を等しく分割する

Question

多くの別個のコンポーネントがあるグラフが表示されます。各コンポーネントは二部構成です。頂点を2つのセットAとBに分散させるにはどうすれば2つのセットの違いが最小になるのでしょうか？

例：

1：1 -> 2 ->3 -> 4 -> 5

2：6 -> 7 -> 8

最善の解決策である

A = {1, 3, 5, 7}

B = {2, 4 ,6, 8}

T彼は、他の（非最適）溶液を

A = {1, 3, 5, 6, 8}

B = {2, 4, 7}

グラフは、多くの別々の二部構成部品を持っていたときにどのようにこの問題を解決しますでしょうか？

Answer 1

少し偽装されたPartition Problemです。すべての二部構成要素に対して、独立した集合の要素数の差を取る（実際には絶対値です）。これはパーティションの問題への入力です。あなたの例では、[1,1]（（3-2）と（2-1）から）

解決策をグラフに戻すために、セットS1で終了したすべてのグラフについて、より大きなセットをAに入れてください（Bの方が小さい）。S2で終わったすべてのグラフについて、より小さいセットをAに入れてください。そして、Bで大きくなります。 、解はS1 = [1]であり、S2 = [1]である。関連するグラフに戻ると、あなたの例から最適な解決策が得られます。

Answer 2

NPの完全なパーティション問題のバリエーションです。

各コンポーネントについて、どちらの側にも頂点の数、たとえば[m、n]を見つけて、プールAまたはプールBにmを入れるかどうかを決める必要があります。プールBのそれは最小である。

動的プログラミングとIPPのバリエーションによって、この種の問題を解決するための既存の手法があります。しかし、多数のコンポーネントがあると、NP完全性のみで運命づけられます。