最大クリーク問題を解くアルゴリズムの新提案

発表者:
谷 研究室
原田英幸

発表内容

最大クリーク問題解説

研究の目的と背景

用語と定義

解を求めるアルゴリズム解説

伝統的な基本アルゴリズム

電気通信大学富田教授グループのアルゴリズム

独自に考えたアルゴリズム

最大クリーク問題解説

研究の目的と背景

用語と定義

解を求めるアルゴリズム解説

伝統的な基本アルゴリズム

電気通信大学富田教授グループのアルゴリズム

独自に考えたアルゴリズム

最大クリーク問題とは

無向グラフ中の部分グラフの中で、完全グラフでサイズが最大のものを選び出す、組み合わせ最適化問題の一種

NP困難…グラフサイズが大きい→計算時間が膨大

↑黄色が最大クリーク

研究の背景と目的

NP困難…高速なアルゴリズムの存在が重要

グラフ理論は応用の幅が広い

大きいグラフ…計算不能
↓
計算可能にする

一番関係が親密な集合を
抜き出したいなぁ・・・

何かのデータの関係をグラフとして表した

研究の方針

従来のアルゴリズムを解析

長所・短所・改良点?

従来アルゴリズムVS改良アルゴリズム

処理時間比較

各アルゴリズムがどのようなグラフに対して有効か

密なグラフで速いか?

疎なグラフで速いか?

最大クリーク問題解説

研究の目的と背景

用語と定義

解を求めるアルゴリズム解説

伝統的な基本アルゴリズム

電気通信大学富田教授グループのアルゴリズム

独自に考えたアルゴリズム

用語

近傍:ある頂点に隣接する頂点全ての集合

点誘導部分グラフ:あるグラフから適当な頂点集合を選んで、その頂点集合とそれらの間に存在する辺で構成されるグラフ

v

による点誘導部分グラフ

: の近傍

用語

クリーク:完全グラフを誘導する頂点集合

極大クリーク:他のクリークの真部分集合でないクリーク

最大クリーク:グラフ中で頂点数が最大のクリーク

クリーク

極大クリーク

最大クリーク

最大クリーク問題解説

研究の目的と背景

用語と定義

解を求めるアルゴリズム解説

伝統的な基本アルゴリズム

電気通信大学富田教授グループのアルゴリズム

独自に考えたアルゴリズム

基本アルゴリズム

1990年R.CarraghanとP.Paradalosによって提唱された単純なアルゴリズム

「候補節点集合」:ある時点で保持しているクリークに付け加えても、またクリークとなるような頂点の集合

候補接点集合中の頂点をクリークに追加
→サイズ のクリークを作って候補節点集合を更新

:候補節点集合

:保持するクリーク

探索木

1

2

6

4

3

5

１

1,2

1,3

1,2,3

Start

2

2

6

4

3

5

１

2,4

略

(A)

(A)

(B)

(B)

探索木全体を書くと、頂点数の割りに膨大なサイズになる

:候補接点集合

:保持するクリーク

:候補接点集合から
取り除いたノード

初期状態では候補接点集合は頂点全体

最大クリーク問題解説

研究の目的と背景

用語と定義

解を求めるアルゴリズム解説

伝統的な基本アルゴリズム

電気通信大学富田教授グループのアルゴリズム

独自に考えたアルゴリズム

彩色とは

各頂点に番号を割り振り、隣接する頂点には同じ番号を割り振らないようにする

k彩色問題…NP完全

近似彩色…多項式時間(3近似)

3

4

5

2

1

2

1

5色で彩色→

彩色による分岐限定
(富田教授のアルゴリズム)

割り振られた番号の大きい順に、候補接点集合から取り出す

割り振られた番号は、その頂点を中心として候補接点集合内でできるクリークサイズの上界

4

2

3

5

1

3

1

2

1

2

3

1

3

1

2

1

ここから作れるサイズは3

4

2

3

5

1

3

1

2

1

2

3

1

3

1

2

現在の最大サイズ:5

探索木深さ1の時点で6個の子を探索打ち切りできた
これらの頂点で作る極大クリークが全列挙される過程を全て飛ばす

保持する現在最大のクリーク

中略

1にサイズ3を加えても、現在最大の5には届かない

最大クリーク問題解説

研究の目的と背景

用語と定義

解を求めるアルゴリズム解説

伝統的な基本アルゴリズム

電気通信大学富田教授グループのアルゴリズム

独自に考えたアルゴリズム

独自開発のアルゴリズム
(上界を下げる)

サイズ 以上のクリークを作るには、次数 以上のノードが 個以上必要

候補節点集合を次数について降順で整列し、 が 番目のノードの次数 以上となる最小の変数 に対して、 番目のノードの次数 は候補節点集合中のクリークサイズの上界となる

サイズ4→各次数3以上

非常に短時間で頂点集合のクリークサイズの上界を求めることができる

3

3

5

5

2

2

この候補節点集合からできるクリークサイズの上界は4

index 1 2 3 4 5 6

degree 5 5 3 3 2 2

候補接点集合を次数に付いて降順で整列

↑上界6以上のノードが1個

↑上界6以上のノードが2個

↑上界4以上のノードが3個

↑上界4以上のノードが4個

独自開発のアルゴリズム
(隣接ノード上界)

各頂点 に変数 を割り当てる

の近傍と の和集合を次数について降順で整列し、 が 番目のノードの次数 以上となる最小の変数 に対して、 番目のノードの次数 を とする

は を含んだクリークサイズの上界となる

Precondition: neighbor of is sort in descending order.

独自開発のアルゴリズム
(隣接ノード上界)

の大きい順に候補節点集合から取り出して、保持するクリークに加える

取り出す頂点の に基づいて探索打ち切りが可能

先程の候補節点集合の上界を求める際に、次数+1の代わりに使える

6

5

7

8

5

5

4

5

2

5

5

5

5

5

4

4

4

2

次数+1で見る各ノードを含むクリークサイズの上界

addegで見る各ノードを含むクリークサイズの上界

比較結果と考察

対象データ:DIMACSベンチマークグラフ

頂点数50-1500、辺密度0.05-0.99程度

実行環境

OS: Linux version 2.6.9-1.6_FC2

CPU: Intel Pentium4 2.66GHz

RAM: 1024MB

コンパイラ: g++ 3.3.3

C++クラスライブラリLEDA4.5を使用して実装

(富田教授のアルゴリズムは自分で実装したもので、
実際の富田教授のグループの実験結果よりも遅いです)

比較結果と考察

疎なグラフにそこそこ強く、密なグラフにとんでもなく弱い

(密なグラフに強いアルゴリズムは多いらしい)

良い所の主張

各ノードが「そのノードを含むクリークサイズの上界」のデータを持っていれば、応用可能である。

候補節点集合に対する上界の探索にかかる手間が非常に少なく、2回目以降の探索は続きからできるので、手間の割に効果のあるアルゴリズムができた。

終わり

動作の図解

処理TOPのR

クリークQ

現在のR

Rから削除

動作の図解

略

処理TOPのR

クリークQ

現在のR

Rから削除

次数による分岐限定
(江口氏のアルゴリズム)

次数 未満の頂点を含むクリークは、サイズ 以上のクリークとなることはない
↓

未満の次数の頂点を削除していくことにより、グラフ自体を小さくしていく

となる頂点 を候補接点集合から選ばない。

富田教授のアルゴリズムに上記の2つの処理を加えて高速化を図る。

最大クリーク問題解説

研究の目的と背景

用語と定義

解を求めるアルゴリズム解説

伝統的な基本アルゴリズム

電気通信大学富田教授のアルゴリズム

中央大学江口氏のアルゴリズム

独自に考えたアルゴリズム

彩色による分岐限定
(富田教授のアルゴリズム)

次数の小さい頂点から順に、隣接する頂点同士には同じ番号を割り振らないように、できるだけ小さい番号を割り振る

近似彩色になる(確実には最小にならず)

4

2

3

5

1

3

1

2

1

1

3

4

4

4

4

5

6

7

大きいクリークを早いうちに見つける
↓

候補接点集合を取り出す順番を変える

グラフに基準となる情報の付加
(使用メモリ増大・処理高速化)

サイズ4を既に見つけた

上界4以下の頂点と頂点集合を全て無視できる

NP困難:クラスNPに属する任意の問題が、そのNP困難な問題に多項式還元できるような問題

クラスNP:非決定性アルゴリズムで多項式時間で解ける問題はクラスNPに属する

多項式時間:O(nk)以下

NP完全:クラスNPに属していてNP困難

問題Aを問題Bに多項式還元可能:

問題Aの入力を問題Bの入力に多項式時間で変形するアルゴリズムが存在し、その入力に対する問題Bの出力をもとの入力に対する問題Aの出力に多項式時間で変形するアルゴリズムが存在する

(問題Bが解ければ問題Aも多項式時間の処理でそれを利用して解ける)

原田 英幸

2005-04-12T00:19:26