Permutationグラフと Distance-Hereditaryグラフの再構築アルゴリズム清見礼 ○斎藤寿樹上原隆平（JAIST 仲良し3人組）グラフ再構築問題  グラフG=(V, E)のDeck: グラフの多重集合{G-v | v∈V}  グラフの多重集合DのPreimage: DをDeckとするグラフ GのDeck v1 v4 v1 v2 v3 v5 v3 v5 Preimage v2 v4 v2 v4 G-v2 v1 v3 v5 グラフG v3 v5 G-v1 G-v4 v2 v4 v1 v2 v1 v5 v3 v4 G-v3 G-v5 グラフ再構築問題  入力：n-1頂点のn個のグラフD  質問：DをDeckとするPreimageは存在するか? 入力：D ラベルなしグラフグラフ再構築予想  n-1頂点のグラフがn個与えられたとき(n≧3)，それをDeckとするPreimageは高々一つ入力：D 上のグラフとは異なるグラフグラフ再構築予想  UlamとKellyによって提唱 [1957年]  未解決問題  予想が成立するグラフクラス  正則グラフ、木、非連結グラフなど関連研究  再構築可能なもの(一意に決定)  次数列、彩色数など  グラフの同型性判定問題と深い関係  再構築問題は同型性判定問題以上に難しい単純なグラフ再構築アルゴリズム 1. 2. 3. 4. Gi∈Dを選択 Giに頂点vとvに接続する辺を追加（Giv） GivのDeck Divを作る DivとDが等しいかをチェック(Deck Checking)  等しければ，DのPreimageはGiv  等しくなければ，2に戻る入力：D GivのDeck v グラフGiv 単純なグラフ再構築アルゴリズム 1. 2. 3. 4. Gi∈Dを選択 Giに頂点vとvに接続する辺を追加（Giv） GivのDeck Divを作る DivとDが等しいかをチェック(Deck Checking)  等しければ，DのPreimageはGiv  等しくなければ，2に戻る入力：D v GivのDeck ≠ DはGivのDeckではないグラフGiv 単純なグラフ再構築アルゴリズム 1. 2. 3. 4. Gi∈Dを選択 Giに頂点vとvに接続する辺を追加（Giv） GivのDeck Divを作る DivとDが等しいかをチェック(Deck Checking)  等しければ，DのPreimageはGiv  等しくなければ，2に戻る入力：D GivのDeck = DはGivのDeck v グラフGiv 単純なグラフ再構築アルゴリズム 1. 2. 3. 4. Gi∈Dを選択 Giに頂点vとvに接続する辺を追加（Giv） GivのDeck Divを作る DivとDが等しいかをチェック(Deck Checking)  等しければ，DのPreimageはGiv  等しくなければ，2に戻る候補が指数個多項式時間同型性判定このアルゴリズムは遅い！ 多項式時間アルゴリズムの開発  入力に制限：同型性判定を多項式時間で行えるグラフクラス 入力Dのすべてのグラフが、あるグラフクラスに属する GI-完全：同型性判定問題が一般のグラフと同程度に難しい今回の結果 GI完全なグラフクラス Perfectグラフ HHD-freeグラフ Comparabilityグラフ Chordalグラフ同型性判定が多項式時間今回の発表 Intervalグラフ M. Kiyomi et al. (2009) DistanceHereditaryグラフ Permutationグラフつまらない！アルゴリズムが存在再構築予想が成立 Proper Intervalグラフ Tree Thresholdグラフ Permutationグラフの再構築問題  入力：グラフの多重集合D  各グラフGi∈DはPermutationグラフ  質問：DをDeckとするグラフが存在するか？入力：D Permutationグラフ・・・ Permutationグラフ ライン表現を持つグラフクラス 1 2 3 4 5 6 1 6 4 3 6 4 1 5 ライン表現 2 3 2 5 Permutationグラフ Permutationグラフの特徴  補題0  Permutationグラフの誘導部分グラフはPermutationグラフ 1 2 3 4 5 6 1 6 4 3 6 4 1 5 ライン表現 2 3 2 5 Permutationグラフ PreimageがPermutationグラフ ⇒ Deckの中のグラフはすべてPermutationグラフ逆は成り立たない！ PreimageがPermutationグラフの禁止グラフ Permutationグラフの禁止グラフ [T. Gallai 1967] これらのグラフとこの補グラフ k≧0 k 2k+3 k+1 k k 2k+3 Preimageが禁止グラフかチェック 2k+2 考えるべき問題  入力：グラフの多重集合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 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 Prime Prime y1 y2 ・・ xi ・・・ x ・ n ・・・ y i ・・・y n グラフH2n アルゴリズム（Preimageがprime） 1. Dの中からPrimeなグラフを探す 2. If PrimeなグラフGiが存在 3. Giのライン表現に線分を追加（O(n2)回） 4. else PreimageがH2n または H2nかチェックアルゴリズム  入力：グラフの多重集合D  各グラフGi∈DはPermutationグラフ 1. Preimageが禁止グラフかチェック  PreimageがPermutationグラフのみを考えるため 2. Preimageがprimeのとき  Preimageのライン表現が一意 3. Preimageがprimeでないとき  Modular Decompositionを用いて、問題を“Preimageがprimeのとき”におとす Permutationグラフとは独立の話 Modular Decomposition  G=(V, E)のmodule M:頂点集合  V＼Mの頂点はMのすべての頂点と隣接, or Mのすべての頂点と隣接しない  module Mがstrong: Mは他のmoduleとoverlapしない  strong moduleの包含関係を木で表現可能 M4 M1 M1 M5 M2 M3 M2 M3 M4 M5 Modular Decompositionとライン表現 M4 M1 M2 M1 M2 M1 M3 M3 M4 M2 M5M5 M3 M M35 M4 M1 MM 2 5 M3 M4 M5  strong moduleを含まないmoduleのライン表現は一意アルゴリズム（Preimageがprimeでない） 1. For グラフGi∈D (i=1 to n) 2. GiのModular Decompositionを計算 3. For strong moduleを含まないmodule M 4. Mのライン表現に線分を追加(O(n2)回) 5. PreimageがH2nやH2nを含むかチェック GI-完全：同型性判定問題が一般のグラフと同程度に難しいまとめと今後の課題 GI完全なグラフクラス Perfectグラフ HHD-freeグラフ Comparabilityグラフ Chordalグラフ同型性判定が多項式時間 Circular-arcグラフ再構築予想が成立？ Intervalグラフ M. Kiyomi et al. (2009) Circleグラフ DistanceHereditaryグラフ Permutationグラフ多項式時間アルゴリズムの開発アルゴリズムが存在再構築予想が成立 Proper Intervalグラフ Tree Thresholdグラフ