ラベル付き区間グラフを列挙するBDDとその応用 ○斎藤 寿樹（ERATO・BDD/ZDD普及協会） 湊 真一（北海道大学，ERATO・BDD/ZDD普及協会 会長 兼務） 夏のLAシンポジウム 2010年7月20日
区間グラフ 多くのアルゴリズムが存在 区間表現を持つグラフクラス 区間の集合 各区間は頂点と対応 ２つの区間に重なりがある ⇔ 対応する頂点間に辺がある 多くのアルゴリズムが存在
提案されたアルゴリズムが実装上高速か？ 計算機実験 出力 偏りのないデータを入力したい 入力 一様ランダムにデータを生成 区間グラフ
単純な区間グラフのランダム生成法 区間グラフは一様に出力されていない 区間をn個ランダムに生成 区間[0, 1]におさまるような，区間をn個ランダムに生成 ０ 1 区間グラフは一様に出力されていない 密なグラフが生成されやすい 本発表：BDDを使って，連結なラベル付き 区間グラフを一様ランダムに生成
BDD (Binary Decision Diagram) 論理関数をグラフで表現 x1 x2 x3 1 x1 x2 x3 F 1 x1 x3 x2 1 ＢＤＤを用いると ・列挙 ・数え上げ ・ランダム生成 ・etc.
n頂点のすべての区間グラフを表現するBDD 論理変数ei, j を用意(1≦i<j≦n) 論理関数 F 辺(i, j)を使う 辺(i, j)を使わない 区間グラフ 区間グラフではない 1 3 2 5 4 1 3 2 5 4 区間グラフ 区間グラフではない F(1,1,1,0,0,1,0,1,1,1) = 1 F(1,1,0,0,0,1,0,1,1,1) = 0
n頂点のすべての区間グラフを表現するBDD 論理関数 FのBDD 例：n=5 e1,2 e1,3 e1,4 e4,5 ・・・ １ １ １ 1
BDDを用いた区間グラフのランダム生成 n頂点の区間グラフをランダム生成できる ランダム生成アルゴリズム (Knuth, the art of computer programming, vol. 4.1) 解の数を数える BDDをボトムアップに探索 変数に{0, 1}を割り当てる トップダウンに割り当て “偏った”コインフリップ 解の数の割合 541 238 303 167 136 102 98 69 67 35 n頂点の区間グラフをランダム生成できる 1
構築したBDDの応用 ∧ n頂点の区間グラフのランダム生成 辺の数や次数を制限したものもランダム生成できる 1 1 1 1 5頂点のすべての区間グラフを表現するBDD 1 辺の数が6以下のすべてのグラフを表現するBDD 1 ∧
構築したBDDの応用 n頂点の区間グラフのランダム生成 区間サンドイッチ問題(NP-完全問題)がBDDサイズ の線形時間で解ける 辺の数や次数を制限したものもランダム生成できる 区間サンドイッチ問題(NP-完全問題)がBDDサイズ の線形時間で解ける
区間グラフのBDDの構築手法 時間がかかる！ ∨ 区間グラフを列挙 効率のよい列挙アルゴリズム [清見, 来嶋, 宇野, 2006] グラフの数は指数個 時間がかかる！ 構築中のBDD 1 e1,2 1 e1,3 e1,4 e1,5 e4,5 ・・・ 1 3 2 5 4 ∨ 出力したグラフ
区間グラフのBDDの構築手法 区間グラフの認識アルゴリズムは複雑 簡単にはできない 区間グラフを列挙 論理関数Fを論理式で表現 効率のよい列挙アルゴリズム [清見, 来嶋, 宇野, 2006] 論理関数Fを論理式で表現 論理変数のみを用いて，区間グラフの認識を行う 簡単にはできない 区間グラフの認識アルゴリズムは複雑 最も単純なアルゴリズム：LexBFSを用いたアルゴリズム (Corneil, et. al., SODA, ’98)
計算機実験 区間グラフを列挙して，BDDを構築 計算機環境 CPU Memory プログラミング言語 BDDパッケージ Quad-Core 3.1GHz Memory 528GB プログラミング言語 C BDDパッケージ BemⅡ 頂点数 区間グラフの数 BDDのノード数 計算時間 (sec) 3 4 0.08 35 18 0.11 5 541 114 0.60 6 13062 1259 9.56 7 444767 17194 50 8 19912657 246630 3158 9 11121041222 3938791 269971 約3日強 約2800倍
計算機実験 頂点数 7 辺の数m以下（x軸） ・区間グラフの数 ・BDDのサイズ
計算機実験 ノード数：650712 (約12 Mbyte) BDDサイズの変化 (n=8)
今後の課題 区間グラフを表現するBDDについて BDDを構築しないで、区間グラフのランダム生成 ラベルなしグラフのランダム生成 区間グラフを列挙せずに構築可能か？ 区間グラフの認識を論理変数のみで行えるか？ n-1頂点のBDDを使って，n頂点のBDDが作れないか？ 区間を論理変数で表現する？ 非連結な区間グラフのBDD BDDを構築しないで、区間グラフのランダム生成 解の数を数える手法の考案 ラベルなしグラフのランダム生成 どのようにBDDの表現するか？
辺の数m 辺の数m以下の区間グラフ数 BDDのノード数 辺の数mの区間グラフ数 6 15967 1718 7 48202 5015 32235 4614 8 98497 8959 50295 7536 9 169302 12393 70805 9257 10 246372 15733 77070 10832 11 314643 17840 68271 10684 12 365848 18764 51205 8859 13 403018 18991 37170 6807 14 425908 18753 22890 4945 15 437283 18302 11375 3192 16 442155 17726 4872 1807 17 444045 17434 1890 899 18 444640 17316 595 431 19 444745 17225 105 141 20 444766 17201 21 40 444767 17194 1 頂点数7 辺の数を制限したときのグラフの数とBDDのサイズ
計算機実験 頂点数7 次数を制限 ・グラフの数 ・BDDのサイズ 次数d すべての頂点の次数がd以下のすべての区間グラフの数 6 444767 17194 5 334740 16757 4 151410 11892 3 40320 5494 2 2520 1350 頂点数7 次数を制限 ・グラフの数 ・BDDのサイズ