最大重みクリーク抽出法における彩色による上界の実験的評価

最大重みクリーク問題

与えられた無向グラフの頂点集合であって，どの2頂点も辺で直接結ばれているようなものをクリークといいます．各頂点に対して重みという数値が割り当てられているグラフにおいて，クリークであって重みの総和が最大になるものを見つける問題を最大重みクリーク問題といいます．この問題はNP-hardに属する難しい問題です．

分枝限定法

この問題を効率よく解くために，分枝限定法という方法を用います．例えば頂点Aを含むか，含まないかで場合分けをして，細かく問題を分割していきます．このとき，分割されたそれぞれの部分問題に対して，その部分問題が最適解になる可能性があるか？を判定していきます．ここで，見込みがないと判定された部分を捨てていくことで，高速化が期待できます．

頂点彩色による判定

さて，このためには判定を高速に行うことが必要です．本研究では，判定方法として，貪欲法による頂点彩色を用いる方法を利用しました．隣り合う頂点が同じ色にならないように色を塗ったとき，クリーク内の頂点が同じ色にならないという性質から，うまく判定を行います．従来法では，次数の大きい順に彩色を行う方法が用いられていますが，提案法では，Smallest Last Order という異なる順序付けを用いた彩色を行いました．

実験結果

ランダムグラフに対して実験を行った結果，主に辺数の少ない疎なグラフにおいて，従来法よりも高速に計算できることがわかりました．しかし，密なグラフに対してはかえって遅くなってしまうという結果が出ました．

改善案として，様々な判定方法を組み合わせてみること，細かな処理をブラッシュアップして高速化させることなどが考えられます．