この分野のバイブルと言えば、その名もずばり「Graph Classes: A Survey」でしょ
う[BLS99]。この本はすでに知られたクラスの包含関係や
特徴などをかなり詳しく調べてまとめてあるのですが、出てくるクラスの数は約160個、参考文献の数
は約1100本、と大変な量です。でも特定のクラスに限ってよく調べてみると、
まだまだいいネタはあります。そのあたりは最後に…。
LAの会誌にすでに2回ほど書かせていただきましたが、非常に幸運なことに、 私は現在駒澤大学の在外研究制度を利用して Canada の University of Waterloo に滞在させていただいております。延長申請も無事通りまして、 滞在2年目に突入しました。初めてのカナダの冬も体験し、 すっかりカナダ人になってしまったので、どこが日本と違っているのかも、 もうわからなくなりました。…というのは嘘で、やっぱり子供に 「お父さんの英語の発音は悪い」と言われています。
それはさておき、この冬はカナダも暖冬でした。Waterloo 近辺では日中の最高 気温もたった-13度までしか下がりませんでした。オーロラも一回しか出なかっ たし、しかも不幸なことにその夜は私は寝てました(これは一生の不覚!!)。 『タオルを濡らして夜のベランダで振り回して棒を作る』というお約束の遊び (?)も1回で飽きました。でも4月の三寒四温は極端で、4月16日の最高気温は28度、 天気は快晴で、4月22日の最高気温は3度、天気は雪でした。 カナダでは天気予報をきちんと確認しないと 危険です…。
ところで最近、国際会議で日本の研究者に会うと 『上原君最近何やってるの？ カナダで遊んでるの？』 と聞かれることが多くなりました。うむ、これはいけません。 以前から私は Randomized Algorithm に凝っているのですが、 最近は Markov chain Monte Carlo に凝っています。 これについてもいろいろと話題はある(Path coupling, conductance, canonical path, multicommodity flow, balanced almost-uniform permutation といった言葉にピンと来た人はメール下さい。文通しましょう:-) のですが、今回は私が凝っているもう一つの分野、Graph Class の 簡単なサーベイをさせてもらうことにしました。 この世界はかなりマニアックなので、 LAの会誌と言えどもたくさんの人には受けないかもしれない、と思っていた のですが、5月末日に Big News も飛び込んで来たので、 それだけでも紹介する価値はあると思います。 また、たとえ数人でも、マニアな部分にビビっと来る人がい ることを期待しつつ…。
この分野のバイブルと言えば、その名もずばり「Graph Classes: A Survey」でしょ
う[BLS99]。この本はすでに知られたクラスの包含関係や
特徴などをかなり詳しく調べてまとめてあるのですが、出てくるクラスの数は約160個、参考文献の数
は約1100本、と大変な量です。でも特定のクラスに限ってよく調べてみると、
まだまだいいネタはあります。そのあたりは最後に…。
さてこの経典の表紙(右図)を見ると、グラフのクラス間の包含関係が 図示されているのですが、一部がタイトルで隠されていて、ハガユイです。 この図は門外不出の秘伝ではなく、 Webで公開されています。 これを印刷して壁に貼って、毎日拝めば論文が書けます。 ちなみに私がこの図を発見したのは偶然なのですが、 この発見プロセスも結構有用な情報を含むのでここでお知らせしておきます。
なんとすでにこの本に出てくるクラスのデータベースや、クラス間の包含関係を 自動的に描画するプログラムまで作られていて、しかも公開されているのです。 経典の表紙の図は、このシステムの出力なのです。なんともすごい。
Graph Class の業界(?)でもっとも上位にあるのが Perfect Graph です。 定義を書いておくと、最大クリークのサイズをω(・)、 最小の彩色数をχ(・)と書く (まわりに日本語のグラフ理論の本がないので、もしかして標準的な訳語 じゃないかもしれません)と、
あるグラフGが Perfect ←→すべての導出部分グラフ Hがω(H)=χ(H)を満たす
です。Perfect Graph に関しては Strong Perfect Graph Conjecture (SPGC)と 呼ばれる以下の予想があり、この分野での有名な未解決問題です。
あるグラフGが Perfect ←?→ Gは、C2k+1と co(C2k+1)を 導出部分グラフとしてもたない
このSPGCにおいてはP4構造(4頂点の chordless path、つまり (v1,v2,v3,v4)なら {v1,v3}や {v2,v4}をもたないもの)が 重要な役割を果たしている、と考えられていて、 この構造に関してかなり活発な研究が行なわれています。 例えば最近、4-uniform な hyper graph が与えられたとき、 これがあるグラフのP4構造になっているかどうかを 判定する多項式時間アルゴリズムが示されました[HHR02]。 これは今まではかなり限定されたクラスに対してしか示されていませんでした。
なお私自身は『完璧』にはほど遠いグラフのクラスしか研究対象にしてないので、 これ以上の詳細や背景に興味のある方は、 Perfect Problemsというすごい名前のWebページや、 さらにすごい名前の Perfect PeopleというWebページを参照して下さい。
付記…などと調子に乗って書いていたら、5月末日に SPGC が解けたというニュースが飛び込ん できました。詳細は Webページを 御覧下さい。錚々たるメンバーが名を連ねており、 どうもかなり確実な話のようです。いやはや、驚きました。
部分k-木(Partial k-tree の訳はこれでいいのでしょうか？) とは、木を拡張した概念です。いろんな定義があるのですが、 ここでは以下の定義を紹介しておきます。
最後がkじゃなくてk+1なのは、普通の木を1-tree にするためです。
近年、部分k-木の上でさまざまな問題が多項式時間で解けることが示されていま す。これは上記の定義から見え隠れするように、多くの局面で dynamic programming の手法が使えるからです。非常にいいかげんな言い方をすれば、 Tをそれぞれの頂点で切断してやると、そこを通る部分木の数が 高々k+1個しか ないので、この切り口における状態の数も定数個になる、というのがポイントです。
また大御所Bodlaender氏の「定数kに対しては、部分k-木の認識と、 上記の『表現』が線形時間で計算できる」という結果も効いています。 このあたりについては、Bodlaender氏の二つの解説論文 [Bod93,Bod98]が お勧めです。どちらも 彼のWebページから入手で きます。 また同氏の線形時間アルゴリズムはParameterized Complexityの 本[DF99]にも詳しく載っています。それから最新の結果に ついては G馬大学のY崎浩一氏に聞くのがよいでしょう(←無責任)。
chord (弦)とは、cycle や path 上の2つ以上離れた頂点を結ぶ辺のことです。 私はどうしたことか chordal graph やその仲間が大好きです。 chordal graph は分野によっては triangulated graph, rigid circuit graph とも呼ばれていて、いろいろなところに顔を出すグラフです。 おそらくもっともよく知られた定義は
グラフがchordal←→長さ4以上のサイクルはchordをもつ
でしょう。しかしここではもっと違った特徴づけや、 chordal graph の仲間たち、 さらにそれらのいろいろな特徴づけを紹介します。 ここからが本番のつもりだったのですが、 前ふりだけでスペースがなくなってしまったのでごく簡単に。
頂点をv1,v2,…,vnと順番に並 べます。ここでは辺{vi,vj}があっ てi<jのとき、viを親、 vjを子と呼ぶことにしましょう。このとき、
グラフがchordal←→ある頂点の順序が存在して、 すべての親に対して、子供たちはクリークを導出する
となります。また この順序のことを Perfect Elimination Ordering (PEO)と呼びます。
PEOによる特徴づけを利用すると、与えられたグラフが chordal graph で あるかどうかを判定する問題が線形時間で解けます。 これには代表的なアルゴリズムが二つあり、一つは Rose, Tarjan, Lueker らによる Lexicographic Breadth First Search (LexBFS)[RTL76]で、もう一つは Tarjan, Yannakakis らによる Maximum Cardinality Search (MCS) [TY84]です。 特に LexBFS は非常に詳しく調べられています [Sim95,Pan96]。
また最近 LexBFS を使うと、chordal グラフ以外にもいろいろなグラフが効率よく 認識できることがわかってきました。例えば interval graph の認識は LexBFSに ちょっと手を加えたものを5回走らせるだけです[COS98]。 ちなみにこのアルゴリズム、それ自身はかなり単純なのですが、 正当性の証明が相当大変で、full paper は現在約70ページ、 まだ revise 中だそうです(Corneil氏に直接聞きました。 17ページじゃなくて？と聞き直してしまいました:-)。 まさにマニア。 他にもConvex graph[HMPV00], Distance Hereditary graph, HHD-free graph, HHP-free graph [BLS99](Chapter 5)などがある のですが、あまりにもマニアックなのでこれくらいで。
Chordal graphには、部分k-木の定義とよく似た、 とても単純な定義があります(正確にはこっちの方がオリジナルで、 k-tree の方が後なんでしょうけど…)。 端的に言えば「intersection graph of subtrees of a tree」です。 もう少し丁寧に言うと、
です。なかなか美しい特徴づけですね。この intersection graph のクラスが chordal graph のクラスに一致する、という元の結果は [Bun74,Gav74] にありますが、証明はかなり複雑です。でも実は上記のPEOを使うと、 非常に簡単に証明することができます。これはこれでなかなか面白いのですが、 残念ながらここでは省略します。
最近の私は chordal bipartite graph と strongly chordal graph に 凝っています。これらのクラスは1970年代後半に導入されたもので、 ガウスの消去法など、行列の分野での応用があります。 しかしこれらのクラスの、最も高速な認識アルゴリズムの計算時間は、 O(min{mlog n, n2})という、 なんとも中途半端なものでした。 また同型性判定問題の複雑さも知られていませんでした。 なおこれらの問題は(経典の著者の一人である)Spinrad氏の Open Problem のページにも載っています。 このページはマニアックな問題が満載なので、マニアにお勧めです。
さてこれらのクラスについて最近、より高速な認識アルゴリズムを示すことが できました[Ueh02a]。 またその勢いで、chordal bipartite graph の同型性判定がGI完全であることも 示すことができました[NUT02a]。 さらに、これを少し変更すれば strongly chordal graph の同型性判定問題も GI完全であることを示すことができる、とSpinrad氏に指摘されました。 これでなんとか「遊んでない」ということにして下さい。
この結果中、従来の『隣接行列に基づいた定義』とは異なる、 『頂点の順序に基づいた定義』が非常に効いてきます。 つまりある意味で chordal グラフにおける手法を応用したわけです。 実はそれについて紹介するために長々と前ふりをしたのですが、 ついにスペースがなくなったのであっさり放棄します。 詳しくは本人をどこかでつかまえて聞いて下さい。
最後にこれができたら論文になるよ、という素材をいくつか紹介します。
まず chordal bipartite graph や strongly chordal graph を『自然な intersection graph』として特徴づける、という問題が あります(前出の Sprinrad氏のOpen Problem のページにも載っています)。 上記の勢いをさらに利用すれば簡単か、と思っていたのですが、 これが簡単そうに見えてなかなかの難物です。 chordal グラフの場合は、順序づけられた頂点について、 子供たちの関係だけを考えてやればよかったのですが、 これらのクラスについては、子供たちだけでなく、 孫たちの『包含関係』を考えてやらないといけなくて、 そこで煮詰まっています。 それから以下の二つのクラスは 注目株です(『私だけの』という接頭語つき)。
これは interval graph の bipartite 版です。歴史は古く、1980年代初頭に Harary, Kabell, McMorris らによって導入されました [HKM82]。 でもこのクラスが多項式時間で認識できることも1997年にやっと Müller氏 によって示された[Mul97]くらいで、詳しい性質はあまりわかって いません(ちなみに元の論文[HKM82]の特徴づけには間違いがあるの で、それも要注意です。詳しくはMüller氏の論文 [Mul97]を参照して下さい)。 特に同型性の判定問題については未解決です。 interval bigraph を含む chordal bipartite graph は上記の通りGI完全なのです が、interval bigraph の subclass である convex graph については、同型性が 多項式時間で判定できることが知られています[Che99]。 つまりこのクラスは同型性判定問題の複雑さに関して、境界線上にあります。
Interval graph や convex graph に関する結果を見ていると、 線形時間で認識できそうな気もするし、 同型性も多項式時間でできそうな気がしているのですが、 関連しそうな論文 [COS98,Che99]を 見ると、なかなか…。
これはバイオ系の人達によって導入されたグラフです。 以下の通り interval graph の自然な拡張になっています。
N=φとすれば、普通のinterval graphになります。 Pは Probe、NはNonprobe という意味なのですが、背景や文献は もう一つのマニア本[MM99]や最近の結果 [JS01,MS02] を参照して下さい。
非常にいいかんげんなことを言えば probe interval graph は、 interval graph と interval bigraph を足して2で割ったようなクラスです。 Interval graph がかなり研究されている割には、 これらのクラスはまだあまり研究されていません。 特に probe interval graph は最近のクラスでもあり、 バイオ系の応用もあり、というわけで、なかなかお勧めだと思います。 どなたかいいネタあったら一緒に論文を書きましょう。
|
Last modified: Sat Jun 4 18:16:23 JST 2005
by R.Uehara (uehara@jaist.ac.jp) | 
|