Last modified: Thu Jul 21 08:14:25 JST 2005
modified/maintained by R.Uehara (uehara@jaist.ac.jp)
LA会誌担当の上原先生から記事の依頼を頂き、 せっかくの機会なので私が面白いと思っている事/思った事を記事にしようと考え、 以下の3つまでに絞りました。
興味を持って頂ける割合を考えるならば1番最初の確率ゲームになるのでしょうが、 悩んだあげく3番目の内容にしました。 関心を持って頂ける読者の数は少ないかもしれませんが、 (個人的には)とても面白くかつ重要な分野だと思いますので、 この分野の普及という意味も込めて この機会を借りて簡単な紹介をしたいと思います。
Tree-width はグラフのあるパラメーターで、誤解を恐れず言えば、 そのグラフがどれくらい木に近いかを表しているものです。 Tree-width は、理論上のみならず応用上でも重要なグラフパラメータの1つです。 ここではその歴史や応用の話はほとんど出て来ませんが、 興味をある方は文献[bod98,bod05]をご参照下さい。
Tree-width は理論的に見ても非常に魅力的なグラフパラメーターで、 「自然」でかつ「良い性質」を持っています。 「自然」という意味は、様々な特徴付けを持つということです。 例えば、 コーダルグラフやk-treeなどの木構造を持つグラフによる特徴付けや、 fugitive search game や robber and cops game などの ゲームの視点からの特徴付けや、 bramble や tangle などの他の(双対的な)グラフパラメーターによる特徴付け などが挙げられます。 「良い性質」とは、 グラフマイナープロジェクトで有名な、 tree-width が高々kであるグラフの集合に対する 有限個の obstruction set による特徴付けや、 ミニマックス定理が存在するなどです。 有限個の obstruction set による特徴付けは、 Fixed Parameter Tractable (FPT) と深い関わりを持ちます。 またミニマックス定理は、 複雑で難解な定理をすっきりした分かり易い形に書き換えるための 手助けになりますし、 tree-width の下界を求める強力な武器にもなります。 ここでは、tree-width の下界について少し紙面を割きたいと思います。 そのために、先ずミニマックス定理について説明します。
比較的良く見かける tree-width の定義は decomposition を使ったものです。 先ずグラフGに対し、decomposition というものを定義します。 このときGに対して沢山の decomposition が考えられるので、 Gに対する decomposition の集合をＤ(G)で表しましょう。 decomposition Dを決めるとそれに対しある値δ(D)が決まります。 Gのtree-width tw(G)はminD∈Ｄ(G)δ(D)で与えられます。 一方、bramble を使っても tree-width は定義できます。 先ずグラフGに対し、bramble というものを定義します。 ここでもGに対して沢山の bramble が考えられるので、 Gに対する bramble の集合をＢ(G)で表しましょう。 bramble Bを決めるとそれに対しある値β(B)が決まります。 このとき tw(G)はmax{B∈Ｂ(G)}β(B)で与えられます。 結局 minD∈Ｄ(G)δ(D)=tw(G)=max{B∈Ｂ(G)}β(B) となり、これが tree-width のミニマックス定理と呼ばれるものです。
このミニマックス定理により、 「存在しない事」を示す作業を、 「存在する事」を示す作業に代替できるようになります。 つまりミニマックス定理により、 ある bramble Bを構築し、それに対する値β(B)を計算する事によって、 tree-width の下界を構成的に得ることができます。 この方向での研究は、最近 Bodlaender等により行われています[bgk05]。
大雑把に言うと、上記で述べたような"双対的"な構造がある世界では、 良い近似が期待できます(何故なら良い下界が 得られ易いからです)。 しかし、不思議な事に tree-width に対しては今現在、 (多項式時間近似アルゴリズムとして) 対数近似しか知られていません。 一般のグラフに対し、定数近似を持つか否かは重要な未解決問題となっています。
Branch-width も tree-width と同様重要なグラフパラメータの1つで、 巡回セールスパーソン問題などに応用を持ちます。 両者はともにグラフマイナープロジェクトにおいて重要な役割を果たしています。 この両者はある意味よく似ていて、思い切った言い方をすれば、 本質的に同じものだとも言えます。 実際、グラフGに対する branch-width を bw(G)で表すと、 bw(G)≧2の場合 bw(G)≦tw(G) + 1≦[3/2 ・bw(G)]([]は小数切捨てです;上原注) という関係が成り立ちます。 また branch-width は tree-width 同様に、ミニマックス定理を持ちます。
(本段落で書かれていることは客観性に欠けるかもしれません。) これからはどうなるか分かりませんが、少なくともこれまでは、 branch-width よりtree-width の方が親しみやすいパラメータだったと言えます。 その理由の1つに、(それまでの知識量にもよりますが) tree-width の定義程 branch-width の定義は直観的では無いからです。 (かなり主観的ですが) branch-width での「点」の役割は、 tree-width でのそれと比べてかなり小さいです。 逆にbranch-width での「辺」の役割は、 tree-width でのそれと比べてかなり大きいです。 次節でも述べますが、マトロイド的に見ると、 「辺」は要素に対応し、「点」はランクに対応します。 要素は物質的でランクは概念的と言えますが、この概念的なランクを 物質的な「点」とうまく結び付けているところに、 親しみやすい理由の1つがあるように感じられます。 さらにこれは、(物質的な感覚がより必要とされる)グラフアルゴリズムの 構築を考える際には、プラスに働いているように思えます。
前の段落で、branch-width と tree-width との人気(親しみ易さ)の差は これからはどうなるか分からないと述べましたが、 それには幾つかの理由があります。 1つは最近 Paul 等が tree-width の定義と合わせる形で、 branch-width を定義し直したことにあります。 彼らによる新しい定義で tree-width とbranch-width を見比べると、 前の段落で述べた「点」と「辺」の対応関係が分かると思います。 ここでは詳しく述べませんが、興味のある方は文献[pt05]をご参照下さい。 今後の人気の差が縮まりそうなもう1つの理由は、 少し前から branch-width がマトロイド上の重要なパラメータであるという 認識が高まってきている点です。 (広義の意味で) branch-width はグラフのみならず、 グラフの拡張であるマトロイド上でも定義する事ができます。 もっと言うと、connectivity function (空集合を0に対応させる、対称なサブモジュラー関数) が定義されている世界ならば、branch-width を定義する事が可能です。 マトロイドの観点から branch-width の定義を眺めてみると、 そうでないときと比べて、多少自然なものに感じられます。
前節で、branch-width はマトロイド上で定義可能である事を述べましたが、 「tree-width はどうなの?」という疑問が当然生じます。 結論から言うと、それは可能でして、最近 Hlineny 等によって 発見されました[hw03]。 tree-width のグラフからマトロイドへの一般化は一見簡単に思えますが、 実際はそうではありません。 問題は、マトロイドには点と対応する物質的なものがないところにあります。 例えばグラフをマトロイドとして見る場合は、 グラフの世界での物質的な「辺」が マトロイドの世界の物質的な「要素」に対応します。 ここで私が先程から述べている「物質的」という意味は、 物としてとらえる事ができ、1個、2個、…と数える事のできるものを指します。 一方マトロイドの世界で、 グラフの世界での物質的な「点」と対応している、物質的なものはありません。 強いて言うならば、「点」に対応するものに「ランク」が挙げられます。 例えば、頂点数がnで辺の本数がmの連結グラフGを考え、 Gに対するグラフ的マトロイドM(G)を考えてみましょう。 この場合、M(G)の要素数はmになり、M(G)のランクはn-1になります。 「ランク」の実態は数なので、物質的と言うよりは概念的なものと言えます。
ではこの線(点とランクの対応)で、考えをさらに押し進めてみましょう。 「ランク」は「辺集合がスパンしている頂点集合(の個数)」に対応するので、 グラフ上での tree-width の定義においての上記の頂点集合の役割を 注意深く考察する必要が生じます。 実際Hlineny等はそれを行う事で、tree-width の マトロイドへの一般化を可能にしています。 (個人的には、tree-width のミニマックス定理をマトロイドの観点から見直す事に 興味を持っています。)
最近、Oum と Seymour によって rank-width と呼ばれる 新たなグラフパラメーターが紹介されました[o05]。 私もまだ勉強中で詳しくは紹介できませんが、それでも簡単に紹介したいと思います。 その前に準備として少し脇道にそれて、広義の意味での branch-width について 説明したいと思います。
ここまで定義の詳細や式などをなるべく避けた説明を心掛けてきましたが、 ここでの説明でそれを行うとかえって混乱を招く恐れがありますので、 ここでは式を使って説明します。 上述したとおりconnectivity function が定義されている世界ならば、 (広義の意味で) branch-width を定義する事ができます。 そのために必要な基本となる道具は、 以下のようなマトロイドM=(S,Ｉ)、木T、関数f,gです：
このときTの辺eに対し、T＼eは丁度2つの部分木からなります。 この部分木の一方をT1$で表し、 T1の葉の集合をL1で表しましょう。 (fの対称性より、もう一方の部分木は考えなくても良いことになります。) このときf(g-1(L1))を、eの幅と呼びましょう。 さらに、Tの辺の中で最大の幅を持つ辺の、その幅をTの幅と呼ぶことにします。 最後に、沢山考えられるTの中で幅が最小となるTの、 その幅が connectivity function fの branch-width となります。
元々は branch-width といった場合は、 connectivity function fとしてマトロイドの世界で呼ばれる (狭義の意味での) connectivity function : λM(X)=rM(X)+rM(S＼X)-r(M)+1で 定義されたものを指していました。 しかし最近は、先に説明しました(a),(b),(c)を満たす関数を (広義の意味で用いて) connectivity function と呼び、 その connectivity function に対して (広義の意味での) branch-width を考えるようになってきてます。
本節の本題に戻りますが、rank-width は広義の意味での branch-width の 枠組に結果的には含まれてしまいますが、なかなか興味深いパラメータです。 rank-width の定義は、 branch-width の定義の (Tの葉に対応させるオブジェクトである)辺を頂点に取り換え、 connectivity function として、自然に定義できるある行列の (GF(2)上での)ランク関数を採用することで定義できます。 他の重要なグラフパラメーターの1つである clique-width や、 頂点の削除と pivoting と呼ばれる操作により定義される vertex-minor に関係しています。 まだ十分に時間をかけた勉強はできてはいませんが、 個人的にはかなり意味のあるグラフパラメーターではないかと思っています。 (個人的には、bounded branch-width なグラフに対して、Tutte polynomial が 多項式時間で解けることが知られてますが、その焼き直しとして、 bounded rank-width なグラフに対して、 Bollobás等が紹介した interlace polynomial が多項式時間で解けるか 否かという研究に興味があります。)
ごく最近、Oum と Seymourにより(広義の意味での) branch-width の研究に対して 大きな進展がありました。 ある (広義の意味での) connectivity function fと固定されたkに対して、 fの branch-width が高々kであるか否かが、 多項式時間で判定できるという結果です[os05]。 注目されていた大きな問題が解かれてしまいましたが、 研究しなければならないことはまだまだ沢山あります。 今後益々目が離せない分野の一つだと思います。
|
Back to Table of Contents Last modified: Thu Jul 21 08:14:25 JST 2005 modified/maintained by R.Uehara (uehara@jaist.ac.jp) |
|