二部グラフの最大独立セット

Question

格子証りのグラフの最大独立セットを見つけようとしています。

いくつかのメモで以下を見つけました 「1998年5月13日 - ワシントン大学-CSE 521-ネットワークフローの適用」:

問題：

二部グラフが与えられた $ g =（u、v、e）$, 、独立したセットを見つけます $ u ' cup v' $ これはできるだけ大きい場所です $ u ' subseteq u $ と $ v ' Subseteq V $. 。のエッジがない場合、セットは独立しています $ e $ セットの要素間。

解決：

頂点にフローグラフを作成します $ u cup v cup {s、t } $. 。各エッジに対して $（u、v） in e $ から無限の容量のエッジがあります $ u $ に $ v $. 。それぞれのため $ u in u $, 、からユニット容量のエッジがあります $ s $ に $ u $、それぞれのために $ v in v $, 、からユニット容量のエッジがあります $ v $ に $ t $.

有限容量のカットを見つけます $（s、t）$, 、 と $ s in s $ と $ t in t $. 。させて $ u '= u cap s $ と $ v '= v cap t $. 。セット $ u ' cup v' $ カットを横切る無限の容量エッジがないため、独立しています。カットのサイズはです $ | u -u '| + | V -V '| = | u | + | v | - | u ' cup V' | $. 。これは、独立したセットを可能な限り大きくするために、カットを可能な限り小さくするためになります。

それで、これをグラフとして受け取りましょう：

A - B - C
    |
D - E - F

これを次のように二部グラフに分割できます$（u、v）=（ {a、c、e }、 {b、d、f }）$

Brute Forceの検索で、唯一の最大独立セットが $ a、c、d、f $. 。上記のソリューションを試してみましょう：

したがって、構築されたフローネットワーク隣接マトリックスは次のとおりです。

$$ begin {matrix}＆s＆t＆a＆b＆c＆d＆e＆f s＆0＆1＆0＆1＆0＆1＆0 t＆0＆0＆0＆ 0＆1＆0＆1＆0＆1 a＆1＆0＆0＆ infty＆0＆0＆0 b＆0＆1＆ infty＆0＆ infty＆0＆ infty＆0 c＆1＆0＆0＆ infty＆0＆0＆0＆0 d＆0＆1＆0＆0＆0＆ infty＆0 e＆1＆0 ＆0＆ infty＆0＆ infty＆0＆ infty f＆0＆1＆0＆0＆0＆0＆ infty＆0 end {matrix} $$

ここに私が立ち往生している場所があります。私が見る最小の有限容量カットは些細なものです： $（s、t）=（ {s }、 {t、a、b、c、d、e、f }）$ 容量は3です。

このカットを使用すると、次の誤った解決策が得られます。

$$ u '= u cap s = {} $$ $$ v '= v cap t = {b、d、f } $$ $$ u ' cup v' = {b、d、f } $$

一方、私たちは期待していました $ u ' cup v' = {a、c、d、f } $？誰もが私の推論/仕事で私が間違っている場所を見つけることができますか？

Answer 1

最大独立したセットの補体は、最小頂点カバーです。

二部グラフで最小の頂点カバーを見つけるには、参照してください ケーニグの定理.

Answer 2

対抗例で示すように、与えられた解決策は明らかに間違っています。グラフu+vは、無限の容量エッジによって接続されたコンポーネントであることに注意してください。したがって、すべての有効なカットは、同じ側にa、b、c、d、e、fのすべてを含める必要があります。

解決策がどこから来たのかを追跡しようとしています。http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdfアフジャ、マグナンティ、オーリンによるネットワークフローを引用します いくつか 問題の。この本は著作権から外れており、ダウンロード可能です http://archive.org/details/networkflows00ahuj しかし、この問題と解決策は含まれていないようです（「Bipartite」のすべての発生を検索）。

ソリューションの説明段落は、それが構築するグラフの最小のカットがに対応することを示していないことに注意してください。 最大 独立したセット。それは得る方法を示しているだけです an 独立したセット。

それでも、アルゴリズムが何をしようとしているかを見ることができます。実際の最大独立セットが、そのs、tカットの観点から対応するものは次のとおりです。

アルゴリズムを破る無限の容量のエッジが強調されています。

アルゴリズムを意図したものに修正する方法がわかりません。たぶん、無限のエッジのコストは、後方に進むとゼロになるはずです（つまり、SからTに行くところがありますが、T側からS側に交差するのでしょうか？しかし、この非線形性でミニカット/マックスフローを見つけるのはまだ簡単ですか？また、質問から@jukkaSuomelaのソリューションからアルゴリズムへの解決策を橋渡しする方法を考えると、最大マッチングから最小頂点カバーに移動するのが難しいです。 - アルゴリズムのように、フローのようなアルゴリズムを使用して、最小頂点カバーをそこからどのように回復しますか？説明されているように ここ, 、最大マッチングが見つかった後、UとVの間のエッジが最小頂点カバーを見つけるように指示されます。繰り返しますが、これは、この問題を解決するために必要なMIN-CUT/MAX-FLOWの単純なアプリケーションがすべてであることを示していません。

Answer 3

指定されたアルゴリズムは正しいです。構築されたフローネットワークを指示する必要があり、 $ s $-$ t $ カット頂点セットから出て行くエッジのみを考慮します $ s $.

Answer 4

カットは、容量ではなく、実際のフローにある必要があります。 Sからの流れは有限であるため、{s、t}カットは有限になります。残りは上記の説明です。