algorithm - 与えられた二部グラフからすべての最大完全二部サブグラフを見つける

Question

与えられた は二部グラフであり、すべての極大完全二部サブグラフをリストしたいと考えています。

例えば、

頂点集合 L = {A, B, C, D}

頂点集合 R = {a, b, c, d, e}

エッジ: Aa、Ab、Ba、Bb、Cc、Cd、Dc、Dd、De

完全な二部構成の最大値は次のとおりです。

{A,B}-{a,b}

{C,D}-{c,d}

{D} - {c、d、e}

ブルート フォース アルゴリズム O(2^n) を見つけました。近似アルゴリズムかランダム化アルゴリズムかはわかりません。

Answer 1

二部グラフの各部分の頂点のすべてのペアの間にエッジを追加することにより、問題を最大クリークの検出に変換できます。

Bron-Kerbosch アルゴリズムを使用して、グラフ内のすべての最大クリークを一覧表示できます (2 部である必要はありません)。実装は非常に簡単で、O(3^(n/3)) の最悪の場合の時間制限がわずかに優れています。グラフの縮退に関して、修正パラメータの扱いやすい時間制限もあります。