MaxCliqueDynアルゴリズム

開発者:	Insilab（スロベニア国立化学研究所）
開発状況:	アクティブ
言語:	C++
タイプ：	グラフ理論、最大クリークアルゴリズム、クリーク問題
ライセンス：	GNU 一般公衆利用許諾書
Webサイト：	insilab.org/maxclique/

MaxCliqueDyn アルゴリズムは、無向グラフ内の 最大クリークを見つけるためのアルゴリズムです。

MaxCliqueDyn は、制限されたサイズの最大クリークを見つける MaxClique アルゴリズムに基づいています。制限は、カラーリング アルゴリズムを使用して見つけられます。MaxCliqueDyn は、動的に変化する制限を含むように MaxClique を拡張します。

このアルゴリズムは Janez Konc によって設計され、その説明は 2007 年に公開されました。^[1]以前のアルゴリズムと比較して、MaxCliqueDyn は改良されたカラーリング アルゴリズム (ColorSort) を備えており、検索空間の一部に対して、より厳密で計算コストの高い上限を適用します。^[1]両方の改良により、最大クリークを見つける時間が短縮されます。時間の短縮に加えて、改良されたカラーリング アルゴリズムは、最大クリークを見つけるために必要なステップ数も削減します。

MaxCliqueアルゴリズム^[2]は、MaxCliqueDynを拡張した基本アルゴリズムです。このアルゴリズムの 疑似コードは次のとおりです。

手続きMaxClique(R, C)は
    Q = Ø、Q max = Øです。

    R ≠ Øの場合
        集合Rから最大色C(p)を持つ頂点pを選択する
        R := R\{p}
        |Q| + C(p)>|Q max |の場合
            Q := Q ⋃ {p}
            R ⋂ Γ(p) ≠ Øならば
                G(R ⋂ Γ(p))の頂点彩色C'を得る
                マックスクリーク(R⋂Γ(p), C')
            そうでない場合、 |Q|>|Q max |ならばQ max  := Q
            Q := Q\{p}
        そうで
            なければ終了を返す
    

ここで、Qは現在成長中のクリークの頂点の集合、Q _{max は}現在見つかった最大のクリークの頂点の集合、Rは候補となる頂点の集合、C はそれに対応する色クラスの集合です。 MaxClique アルゴリズムは、 Q に頂点を追加したりQから頂点を削除したりして、最大クリークを再帰的に検索します 。

MaxCliqueは近似色付けアルゴリズム^[2]を使用して色クラスの集合 Cを得る。近似色付けアルゴリズムでは、頂点は候補頂点集合Rに現れるのと同じ順序で一つずつ色付けされ、次の頂点pが同じ色クラスのすべての頂点に隣接していない場合はこのクラスに追加され、pが既存の色クラスのすべてで少なくとも1つの頂点に隣接している場合は新しい色クラスに入れられる。

MaxClique アルゴリズムは、色順に並べられた頂点Rを返します。色付きの頂点は、現在のクリーク Qに追加されることはありません。したがって、これらの頂点を色で並べ替えても、MaxClique アルゴリズムには役立ちません。 ${\displaystyle v\in R}$${\displaystyle C(v)<{|Q_{max}|}-{|Q|}+1}$

ColorSort アルゴリズムは、上記の観察を考慮に入れることで近似色付けアルゴリズムを改良したものです。各頂点には色クラスが割り当てられます。 の場合、頂点は集合 Rに移動されます ( Rの最後の頂点の後ろ )。 の場合、頂点は R に留まり、 Rには移動されません 。最後に、(ただし) に残っているすべての頂点は、各頂点に出現する順に、インデックス の昇順で Rの後ろに追加されます 。ColorSort アルゴリズムでは、これらの頂点にのみ色が割り当てられます。 ${\displaystyle C_{k}}$${\displaystyle k<{|Q_{max}|}-{|Q|}+1}$${\displaystyle k\geq {|Q_{max}|}-{|Q|}+1}$${\displaystyle C_{k}}$${\displaystyle C_{k}}$${\displaystyle k\geq {|Q_{max}|}-{|Q|}+1}$${\displaystyle C_{k}}$${\displaystyle k}$${\displaystyle C(v)=k}$

ColorSortアルゴリズムの擬似コードは次の通りである: ^[1]

手順ColorSort(R, C)は
    最大数:= 1;
    k最小 := |Q最大| − |Q| + 1;
    k min ≤ 0 の場合、k min  := 1;
    0 の場合
    C 1  := Ø; C 2  := Ø;

    i := 0から|R| − 1まで
        p := R[i]; {Rのi番目の頂点}
        k := 1;
        C k ⋂ Γ(p) ≠ Øの場合、
            k := k+1;
        k > max_noの場合
            最大数:=k;
            C max_no+1  := Ø;
         
        C k  := C k ⋃ {p}
        の場合終了; k < k minの場合 
            R[j] := R[i];
            j := j+1;
        終了の場合
    終了の場合

    C[j−1] := 0;

    k := k minから max_no までを実行し
        、 i := 1 から |C k |までを実行し、 
            R[j] := C k [i] を実行します。
            C[j] := k;
            j := j+1;
        終わりの終わり
    の

例

上記のグラフは、頂点の候補セットR  = {7 ⁽⁵⁾、1 ⁽⁴⁾、4 ⁽⁴⁾、 2 ⁽³⁾、3 ⁽³⁾、6 ⁽³⁾、5 ⁽²⁾、8 ⁽²⁾ } として記述でき、近似色付けアルゴリズムと ColorSort アルゴリズムの両方の入力として使用できます。どちらのアルゴリズムを使用しても、次の表を作成できます。

近似色付けアルゴリズムは、頂点セットR  = {7 ⁽⁵⁾ , 5 ⁽²⁾ , 1 ^{(4) , 6 ( 3)} , 8 ⁽²⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³⁾ } と、それに対応する色クラスのセットC  = {1,1,2,2,2,3,3,3} を返します。ColorSort アルゴリズムは、頂点セットR  = {7 ⁽⁵⁾ , 1 ⁽⁴⁾ , 6 ⁽³⁾ , 5 ^{( 2)} , 8 (2 ^{) , 4 (4} ) , 2 ⁽³⁾ , 3 ⁽³⁾ } と、それに対応する色クラスのセットC  = {–,–,–,–,–,–,3,3,3} を返します。ここで、– は k  < 3 の未知の色クラスを表します。

MaxCliqueDyn アルゴリズムは、色クラスを決定するために近似色付けアルゴリズムの代わりに ColorSort アルゴリズムを使用することで、MaxClique アルゴリズムを拡張します。MaxClique の各ステップで、MaxCliqueDyn アルゴリズムは、アルゴリズムが現在実行されている頂点に関してR内の頂点の次数も再計算します。次に、これらの頂点は、グラフG(R)内の次数に関して降順でソートされます。次に、ColorSort アルゴリズムは、Gではなく誘導グラフG(R)内の次数でソートされたR内の頂点を考慮します。そうすることで、最大クリークを見つけるために必要なステップ数が最小限に抑えられます。それでも、 R内の次数の決定と頂点のソートの計算コストは​​同じままである ため、MaxClique アルゴリズムの全体的な実行時間は改善されません。${\displaystyle O(|R|^{2})}$

MaxCliqueDynアルゴリズムの擬似コードは次の通りである: ^[1]

手順MaxCliqueDyn(R, C, level)は
    S[level]:=S[level]+S[level−1]−S old [level]です。
    S古い[レベル] := S[レベル−1];

    R ≠ Øの場合
        RからC(p)が最大となる頂点p(最後の頂点)を選択する。
        R := R\{p};
        |Q| + C[Rにおけるpのインデックス] > |Q max |の場合
            Q := Q ⋃ {p};
            R ⋂ Γ(p) ≠ Øの場合、
                 S[level]/ALL STEPS < T limitの場合、 
                    G(R⋂Γ(p))の頂点の次数を計算する。
                    R ⋂ Γ(p) の頂点を降順に並べる
                    学位に関して;
                終了の場合
                カラーソート(R⋂Γ(p), C')
                S[レベル] := S[レベル] + 1;
                すべてのステップ := すべてのステップ + 1;
                MaxCliqueDyn(R ⋂ Γ(p), C', レベル + 1);
            そうでない場合、 |Q| > |Q max |であればQ max  := Q;
            Q := Q\{p};
        そうで
            なければ終了を返す
    

T_制限の値は、ランダム グラフで実験することによって決定できます。元の記事では、アルゴリズムはT_制限 = 0.025 の場合に最適に機能すると判断されました。