Document

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グラフ