フロンティア法の計算量について斎藤寿樹 ERATO湊離散構造処理系プロジェクト研究員フロンティア法固定パラメータアルゴリズム • BDD/ZDDをトップダウンに構築する方法サイズ n の入力とパラメータ k を与えたとき， • s-t パス、サイクル、木（森）など O(f 時間アルゴリズム (c は k に依存しない定数) フロンティア法の計算時間＝BDD/ZDDの構築時間 • 構築するBDD/ZDDが入力の指数サイズ入力サイズの指数時間 c (k)・n ) フロンティア法理論的につまらない？パラメータ k: max |F| (Fはフロンティア) グラフのパス幅固定パラメータアルゴリズムフロンティア法の計算時間 e1 フロンティア F e2 ei e4 s-t パス(KnuthのSimpath)の場合： mate の各要素が取り得る値|F|+1通り mate 配列の取り得るパターンの数(|F|+1)! e2 e3 e3 e3 e3 ZDDのノード数：高々Amax×m s-t パスの場合：構築するZDDのノード数は高々 m×(|Fmax|+1)! ・・・・・・ e1 e 5 e2 e3 各レベルのノード数 A：フロンティア上の mate 値の取り得るパターンの数 m：Gの辺の数 Amax：フロンティアサイズ最大のレベルのノード数（の上界） Fmax：フロンティアの最大サイズ ei 入力のグラフG ei ei ・・・ ei 構築途中のBDD/ZDD 全体の計算：高々 Amax m×(1ノードの生成時間) s-t パスの場合：Fmax Amax m •1つのノードの生成時間：O(Fmax)時間 Fmaxをパラメータとする固定パラメータアルゴリズムフロンティアの最大サイズパス幅（pathwidth）フロンティアの推移例： 1 2 4 3 5 7 6 8 9 入力のグラフ φ 1, 2 1, 2, 3 2, 3 3, 4, 5, 6 3, 4, 5 2, 3, 4, 5 2, 3, 4 4, 5, 6 4, 5, 6, 7 5, 6, 7 5, 6, 7, 8 頂点の部分集合の列 B=(B1, B2, …, Bl) がグラフ G のパス分解(path decomposition) ⇔ 以下の二つを満たす 1. G の各辺{u, v}に対して、u, v∈Bi である Bi が存在 2. u ∈Bi かつ u ∈Bj ⇒ u ∈Bk ∀k (i≦k≦j) Bのパス幅(pathwidth) pw(B)： max |Bi|-1 •グラフGのパス幅：min pw(B) φ 8, 9 7, 8, 9 7, 8 6, 7, 8 フロンティアの最大サイズは次の二つで決まる 1．グラフの形 2．処理する辺の順序パスっぽいグラフはフロンティアの最大サイズが小さいパス幅:パスっぽさを表すパラメータフロンティアの推移パス分解フロンティアの最大サイズパス幅グラフGのパス幅が求められるとうれしい！しかしNP困難（平面グラフ、コーダルグラフでも）