マトロイド不変多項式の基礎今井浩東京大学理学系研究科情報科学専攻科学研究費特定領域研究(B)「アルゴリズム工学」 A01班第1回班会議 1999-06-24 本発表の目的 • マトロイド不変多項式基礎の紹介 – D. J. A. Welsh: Complexity: Knots, Colourings and Counting. Cambridge University Press, 1993. の内容紹介 – Tutte多項式関連の他の参考文献 • T. Brylawski and J. Oxley: The Tutte Polynomial and Its Applications. `Matroid Applications’ (N. White, ed.), Cambridge University Press, 1992, pp.123-225. • 本研究グループの研究成果 • 関連サーベイなど – 数理科学7月号 – アルゴリズム工学信学英文D論文誌特集原稿離散システム不変量論の展開 • • • • • • • • グラフ彩色多項式，フロー多項式ネットワーク信頼性解析結び目Jones多項式, HOMFLY多項式統計物理: 浸透，Isingモデル超平面配置・計算幾何可環代数と組合せ論・計算代数幾何 … BDD: 論理設計・検証 (ACM Kanellakis賞 ’99) マトロイド，ランク関数 • 有限台集合E, ρ: 2E→Z ランク関数 – 0≦ρ(X)≦|X| – ρ(X)≦ρ(Y) (X⊆Y) – ρ(X)+ρ(Y)≧ρ(X∪Y)+ρ(X∩Y) M=(E,ρ) • 行列 A の列ベクトルaiの添字集合E M(A) – ρ(X) = ai (i∈X)の張る空間の次元 (X⊆E) • グラフG=(V,E), V: 点集合, E: 枝集合 M(G) – ρ(X) = 枝集合Xのグラフの点数ー連結成分数独立，従属性 • X: 独立 ⇔ρ(X) = |X| • X: 従属 ⇔ρ(X) < |X| • X: 基 ⇔ρ(E)=ρ(X) = |X| (極大独立集合) • X: サーキット ⇔ 極小従属集合 • X: spanning ⇔ρ(E)=ρ(X) (基を含む) Tutte多項式 • マトロイド M=(E,ρ) T (M ; x, y)   (x 1)  (E) (S )( y 1)|S| (S ) SE • いくつかの点でのTutte多項式の値の意味(1) – – – – T(M;1,1) = 基の数 T(M;2,1) = 独立集合の数 T(M;1,2) = spanning集合の数 T(M;2,0) = グラフのacyclic orientationsの数超平面配置のセル数 Tutte多項式 • いくつかの点でのTutte多項式の値の意味(2) – T(M;1,0) • グラフで1固定点をソースとしたacyclic orientations数 • 超平面配置の有界なセル数 • (－1)ρ(E)T(M;1,0)=μ(M), MのMoebius関数 – T(M;0,2)=totally cyclic orientationsの数 – T (M ; x, y)   (M ): Crapo's  -invariant x x  y 1 – (－1)|E|－ρ(E)T(M;0,－3) • 次数3のグラフの3-edge-coloringsの数 – clique数，edge-connectivity, etc. Tutte多項式 • マトロイド M=(E,ρ) T (M ; x, y)   (x 1)  (E) (S )( y 1)|S| (S ) SE • T(M;1,z+1): spanning集合のサイズの母関数 • T(M;z+1,1): 独立集合のサイズの母関数マトロイド複体組合せ的単体的複体台集合E, Δ⊆2E – e∈E, {e} ∈Δ – X⊆Y∈Δ → X∈Δ 定理．単体的複体がマトロイド複体 ⇔ 基の任意の辞書式順がshelling f-, h-ベクトル  (E)  (E) f (x)   f x  (E) i  h(x 1)   h (x 1)  (E) i i i i 0 i 0 – fi: サイズ i のX∈Δの個数, f-vector – h（x）: shelling多項式, h-vector, internal activity Tutte多項式から変数変換で得られる不変多項式 • • • • • • • • グラフ彩色多項式，フロー多項式ネットワーク信頼性解析結び目Jones多項式統計物理: 浸透，Isingモデル, Pottsモデル超平面配置，(有界な)セル数線形符号のweight enumerator Stanley-Reisner環のHilbert関数 … 彩色多項式(chromatic polynomial) • グラフ G=(V,E) • χ(G;t)=グラフを t 色で塗る仕方の数 • χ(Kn;t)=t(t－1)(t－2)…(t－n+1) • G. D. Birkhoff (1912)：4色問題の代数的取り扱い • Tutte多項式：その一般化 k(G): 連結成分数  (G;t) (1)(E)t k(G)T (M (G);1t,0) • 特性多項式に対応他の多項式 (1) • フロー多項式 F (G;)  (1)| E|(E)T (M (G);0,1) • ネットワーク信頼度 R(G; p)  (1 p)  (E) p| E | (E)T (M (G); 1, 1 ) p • weight enumerator (A: generating matrix of (n,k) code over GF(q)) 1  ( q  1 ) z 1 k n  k A(z)  (1 z) z T (M ( A); , ) 1 z z • Kauffman bracket polynomial of an alternating link L L  A2|V || E |2T (M (G); A4, A4) 他の多項式 (2) • partition function Z of the Ising model with zero external field Z (G)  (2e J )| E |  (E)(4sinh J )  (E)T (M (G); coth(J ), e2J ) • partition function ZPotts of the Potts models K e Q 1 K Z (G)  Q(eK 1)|V | 1 e K | E | T (M (G); ,e ) Potts K e 1 • Gibbs probability μ of the random cluster model | A| p Q   ( A) q ( A)  ( A  E)  (E ) p T (M (G);1 Qq , 1 ) Qq p q                                 双対性 M*=(E,ρ*): Mの双対マトロイド • ρ*(X)=|X|ｰρ(E)+ρ(EｰX) • X: M*の基 ⇔ EｰX: Mの基 • X: M*で独立 ⇔ EｰX: Mでspanning • X: M*のサーキット – Mのコサーキット – 部分集合でそれを除くとランクが減るもので極小 Tutte多項式と双対性 T (M ; x, y)   (x 1)  (E) (S )( y 1)|S| (S ) SE  (E)  (S )   (E)( *(E  S )| E  S |  (E)) | E  S | *(E  S ) |S | (S ) | E | (E)   *(E  S )   *(E)   *(E  S ) T (M ; x, y) T (M *; y, x) 削除・縮約 M=(E,ρ), e∈E • eの削除 M \e  ( X )  ( X ) M \e • eの縮約 M /e  ( X )   ( X {e})   ({e}) M /e Tutte多項式の展開式 T (M ; x, y)   (x 1)  (E)  (S )( y 1)|S| (S ) SE     S  E {e} eS  E T (M \ e; x, y)T (M / e; x, y) (e  loop, coloop) {  xT (M / e; x, y) (e: coloop) yT (M \ e; x, y) (e: loop) Tutte多項式とactivity • マトロイド M=(E,ρ) T (G; x, y)   (x 1)  (E) (S )( y 1)|S| (S ) SE   xi(T ) ye(T ) T : trees • i(T): internal activity, e(T): external activity Internal/external activities (1) 4 3 9 7 5 1 6 8 2 • 木T, 枝順：固定 – 木の枝 e：internal active ⇔ e の基本cutsetで e 最大 – 他の枝 e：external active ⇔ e の基本circuitで e 最大 Internal/external activities (2) 4 3 9 7 5 1 6 internally active 8 2 • 木T, 枝順：固定 – 木の枝 e：internal active ⇔ e の基本cutsetで e 最大 – 他の枝 e：external active ⇔ e の基本circuitで e 最大 Internal/external activities (3) 4 3 9 7 1 6 internally inactive 8 2 • 木T, 枝順：固定 – 木の枝 e：internal inactive ⇔ e の基本cutsetで e 最大でない 5 Internal/external activities (4) 4 3 9 7 externally active 5 1 6 8 2 • 木T, 枝順：固定 – 木の枝 e：internal active ⇔ e の基本cutsetで e 最大 – 他の枝 e：external active ⇔ e の基本circuitで e 最大 Internal/external activities (5) 4 3 9 7 5 1 6 8 2 • 木T, 枝順： internal/external activity i(T)=1, e(T)=1 • 枝 8, 9 の順序を入換え: i=0, e=2 activity, shelling, broken circuit complex • 純な単体的複体(simplicial complex)のshelling – 基(ファセット)全体の全順序がshelling：ファセットを順々に１次元低い純な単体的複体を境界として張り付け可能 • マトロイド複体のshellingでのrestriction – 要素順を逆(小さいが勝ち)にしたinternal active要素の補集合 – shelling多項式 = internal activityの母関数 • broken circuit = circuitで最小要素を除去(要素順固定) – broken circuit complex: broken circuitを含まない集合族の複体 – そのshelling polynomial=マトロイドの特性多項式(彩色多項式) – そのファセット: nbc-base, external activity=0のbase 不変量計算の計算量 • Tutte多項式計算：#P完全 – 一部の特別な場合を除いて(T(M(G);1,1), G=Kn,…) • 既存アルゴリズム(Sekine, Imaiの解析) – 基を列挙してinternal/external activities計算して和 • 基列挙アルゴリズム： • internal/external activities: グラフなら線形時間 • graphic, binary, ternary matroid (Sekine, Imai, Iwata, et al.) • 中規模問題でも実際的に解くアルゴリズム！離散システム不変量計算 ― BDDアプローチ • 2分決定グラフ(Binary Decision Diagram; BDD) – 論理関数を表現するデータ構造 • 変数順重要(有向無閉路グラフ、分岐プログラムの一種) – VLSI CADで多大な成功 • 1999 ACM Kanellakis Theory and Practice賞 R. E. Bryant, E. M. Clarke, Jr., E. A. Emerson, K. L. McMillan • BDDによる離散不変量・数え上げの1つのパラダイムの提示(Sekine, Imai, et al.) – 離散構造活用のトップダウン・出力サイズ依存構成 – 組合せ論を活用したBDDサイズ・幅解析 • 平面分離定理などelimination ordering 符号付きグラフでの展開計算 BDD アプローチグラフのelimination front • G=(V,E), 枝順e1, e2, …, en – i-th elimination front: i 番目までの枝と i+1番目の枝に接続している点の集合 – BDD幅はfrontのサイズのBell数(集合分割数) • G: 平面グラフ – planar separator theoremを再帰的に適用 – n の平方根のオーダのelimination front – BDD幅はこのfrontのサイズのCatalan数格子グラフでのelimination ordering Elimination front サイズは4以下点順からの枝順のよさ • 点に順序をつけ，各枝を点対(小さい方から大きい方への)で表現，その辞書式順を枝順 – i番目までの枝を縮約・削除したグラフでi+1番目の枝が coloop かどうかが簡単に判定可能 – 連結性が保証された場合に，BDDレベルでの2同型性と同型性が一致 elimination order問題点 • Planar separator theoremを再帰的に適用すると，順序でのi番目まで・i+1番目以降の部分グラフの連結性が保持されない – elimination frontのサイズを理論的におさえる際に係数が大きくなる – 格子グラフのような典型例では，両方の部分グラフを連結に保って小さなサイズのfrontを生成できる • 未解決問題： – 一般の平面グラフでelimilation orderで連結性の面でもよい性質を満たすものネットワーク信頼度 R(G,p): グラフG=(V,E)の各枝が確率 p で独立に消滅したとき全体が連結であり続ける確率 • 例1. 三重系 • 例2. K3 (1ｰp)3 (1ｰp)3 +3p(1ｰp)2 +3(1ｰp)2p +3(1ｰp)2p おわりに • アルゴリズム研究の観点から – NP困難問題に対する緩指数時間アルゴリズムの重要性 – elimination order, BDD • 理論的にきちんと解析しにくい • けれども実際に大切なもの • 離散システム研究の観点から – 幾何構造の活用