Permutationグラフと Distance-Hereditaryグラフの 再構築アルゴリズム 　 清見　礼 ○斎藤　寿樹 　 上原　隆平 （JAIST 仲良し3人組）

グラフ再構築問題 Preimage グラフG=(V, E)のDeck: グラフの多重集合{G-v | v∈V} グラフの多重集合DのPreimage: DをDeckとするグラフ GのDeck v1 v3 v5 v4 v1 v2 v3 v5 Preimage v1 v2 v3 v5 v4 グラフG v2 v3 v5 v4 G-v2 G-v4 v1 v2 v5 v4 v1 v2 v3 v4 G-v1 G-v3 G-v5

グラフ再構築問題 入力：n-1頂点のn個のグラフD 質問：DをDeckとするPreimageは存在するか? 入力：D ラベルなしグラフ

グラフ再構築予想 n-1頂点のグラフがn個与えられたとき(n≧3)，それをDeckとするPreimageは高々一つ 入力：D 上のグラフとは異なるグラフ

グラフ再構築予想 UlamとKellyによって提唱 [1957年] 予想が成立するグラフクラス 関連研究 再構築可能なもの(一意に決定) 未解決問題 予想が成立するグラフクラス 正則グラフ、木、非連結グラフなど 関連研究 再構築可能なもの(一意に決定) 次数列、彩色数など グラフの同型性判定問題と深い関係 再構築問題は同型性判定問題以上に難しい

単純なグラフ再構築アルゴリズム Gi∈Dを選択 Giに頂点vとvに接続する辺を追加（Giv） GivのDeck Divを作る DivとDが等しいかをチェック(Deck Checking) 等しければ，DのPreimageはGiv 等しくなければ，2に戻る v グラフGiv 入力：D GivのDeck

単純なグラフ再構築アルゴリズム ≠ DはGivのDeckではない Gi∈Dを選択 Giに頂点vとvに接続する辺を追加（Giv） GivのDeck Divを作る DivとDが等しいかをチェック(Deck Checking) 等しければ，DのPreimageはGiv 等しくなければ，2に戻る v グラフGiv 入力：D GivのDeck ≠ DはGivのDeckではない

単純なグラフ再構築アルゴリズム = DはGivのDeck Gi∈Dを選択 Giに頂点vとvに接続する辺を追加（Giv） GivのDeck Divを作る DivとDが等しいかをチェック(Deck Checking) 等しければ，DのPreimageはGiv 等しくなければ，2に戻る v グラフGiv 入力：D GivのDeck = DはGivのDeck

単純なグラフ再構築アルゴリズム このアルゴリズムは遅い！ 多項式時間アルゴリズムの開発 候補が指数個 同型性判定 多項式時間 Gi∈Dを選択 Giに頂点vとvに接続する辺を追加（Giv） GivのDeck Divを作る DivとDが等しいかをチェック(Deck Checking) 等しければ，DのPreimageはGiv 等しくなければ，2に戻る 候補が指数個 同型性判定 多項式時間 このアルゴリズムは遅い！ 多項式時間アルゴリズムの開発 入力に制限：同型性判定を多項式時間で行えるグラフクラス 入力Dのすべてのグラフが、あるグラフクラスに属する

Distance-Hereditaryグラフ GI-完全：同型性判定問題が一般のグラフと同程度に難しい 今回の結果 GI完全なグラフクラス Perfectグラフ HHD-freeグラフ Comparabilityグラフ Chordalグラフ 同型性判定が多項式時間 今回の発表 Distance-Hereditaryグラフ Intervalグラフ Permutationグラフ M. Kiyomi et al. (2009) つまらない！ アルゴリズムが存在 再構築予想が成立 Proper Intervalグラフ Tree Thresholdグラフ

Permutationグラフの再構築問題 入力：グラフの多重集合D 各グラフGi∈DはPermutationグラフ 質問：DをDeckとするグラフが存在するか？ 入力：D Permutationグラフ ・・・

Permutationグラフ ライン表現を持つグラフクラス 1 2 3 4 5 6 3 6 4 1 5 2 Permutationグラフ 1 2 3 4 5 6 1 6 4 3 2 5 3 6 4 1 5 2 Permutationグラフ ライン表現

Permutationグラフの特徴 逆は成り立たない！ 補題0 1 2 3 4 5 6 3 6 4 1 5 2 Permutationグラフ 1 2 3 4 5 6 3 6 4 1 5 2 ライン表現 1 2 3 4 5 Permutationグラフ 6 PreimageがPermutationグラフ ⇒　Deckの中のグラフはすべてPermutationグラフ 逆は成り立たない！ PreimageがPermutationグラフの禁止グラフ

Permutationグラフの禁止グラフ[T. Gallai 1967] これらのグラフとこの補グラフ k ≧ 0 k 2k+3 2k+3 2k+2 k+1 k k Preimageが禁止グラフかチェック

考えるべき問題 ・・・ 入力：グラフの多重集合D 質問：DをDeckとするPermutationグラフが存在するか？ 入力：D 各グラフGi∈DはPermutationグラフ 質問：DをDeckとするPermutationグラフが存在するか？ 入力：D Permutationグラフ ・・・

Permutationグラフを再構築するアルゴリズム？ DeckのグラフGiのライン表現に線分を追加 指数通りのライン表現が存在 入力：D グラフGi O(n2)通りを試せばOK？ ・・・ ライン表現が一意（高々4通り）に定まるもの

ライン表現が一意のPermutationグラフ 補題1 [T. Ma and J. Spinrad, 1994] PermutationグラフGがmodular decompositionにおいてprimeであるとき、Gのライン表現は一意である 入力：D グラフGi O(n2)通りを試せばOK ・・・

Modular Decomposition Permutationグラフとは独立の話 Modular Decomposition G=(V, E)のmodule M: 頂点集合 V＼Mの頂点はMのすべての頂点と隣接, or 　　Mのすべての頂点と隣接しない module Mがtrivial: M=φ, M=V, or |M|=1 グラフGがprime: Gはtrivialなmoduleしか持たない Prime Mの頂点の隣接関係はMの外を見るとどれも同じ

ライン表現が一意のPermutationグラフ 補題1 [T. Ma and J. Spinrad, 1994] PermutationグラフGがmodular decompositionにおいてprimeであるとき、Gのライン表現は一意である 補題2 [J.H. Schmerl, W.T. Trotter, 1993] グラフGをprimeなグラフとする G-vがprimeであるようなvが存在 ⇔ GがH2nやH2nではない ・・・ x1 x2 xi xn y1 y2 yi yn Prime Prime グラフH2n

アルゴリズム（Preimageがprime） Dの中からPrimeなグラフを探す If PrimeなグラフGiが存在 　　　　 Giのライン表現に線分を追加（O(n2)回） 　 else PreimageがH2n または H2nかチェック

アルゴリズム 入力：グラフの多重集合D Preimageが禁止グラフかチェック Preimageがprimeのとき 各グラフGi∈DはPermutationグラフ Preimageが禁止グラフかチェック PreimageがPermutationグラフのみを考えるため Preimageがprimeのとき Preimageのライン表現が一意 Preimageがprimeでないとき Modular Decompositionを用いて、 問題を“Preimageがprimeのとき”におとす

Modular Decomposition Permutationグラフとは独立の話 Modular Decomposition G=(V, E)のmodule M:頂点集合 V＼Mの頂点はMのすべての頂点と隣接, or 　　Mのすべての頂点と隣接しない module Mがstrong: Mは他のmoduleとoverlapしない strong moduleの包含関係を木で表現可能 M1 M2 M3 M4 M5 M4 M5 M1 M2 M3

Modular Decompositionとライン表現 M4 M5 M3 M5 M4 M5 M1 M2 M3 strong moduleを含まないmoduleのライン表現は一意

アルゴリズム（Preimageがprimeでない） For グラフGi∈D (i=1 to n) GiのModular Decompositionを計算 For strong moduleを含まないmodule M Mのライン表現に線分を追加(O(n2)回) 　 PreimageがH2nやH2nを含むかチェック

Distance-Hereditaryグラフ まとめと今後の課題 GI-完全：同型性判定問題が一般のグラフと同程度に難しい GI完全なグラフクラス Perfectグラフ HHD-freeグラフ Comparabilityグラフ Chordalグラフ 同型性判定が多項式時間 Circleグラフ Circular-arcグラフ 再構築予想が成立？ Distance-Hereditaryグラフ Permutationグラフ Intervalグラフ M. Kiyomi et al. (2009) 多項式時間アルゴリズムの開発 アルゴリズムが存在 再構築予想が成立 Proper Intervalグラフ Tree Thresholdグラフ