by R.Uehara (uehara@jaist.ac.jp)
以前LAの会誌に「グラフマニアの世界」という記事と 「国際会議に行こう!!」という記事を書かせていただきました． あのころはカナダで在外研究をしていて， 『日本の人達に忘れられないように…』という下心で書いていたのですが， 実は2003年4月にこっそりと帰国し，今ではすっかりこき使われております．
カナダから帰ってきて，私は，以下の定理を学びました．
と，必ず何か頼まれる．
- 日本で久しぶりにあった人に「久しぶりです」と型どおりの挨拶をしたら， 相手が，こちらが期待している以上にうれしそうな顔をして，かつ
- 「上原さん忙しいんでしょうね〜」と言われて，謙遜するつもりで 「いやいやそれほどでも」と答える
反例がほとんどない，かなり強力な定理です． これから在外研究に行く人はどうぞ参考にして下さい．
それはさておき，2003年6月にオランダで開催された WG '03 という会議に参加，発表してきました． 開催地がオランダで，主催者が Bodlaender 氏だったので，かつてオランダの Bodlaender 氏のところで 在外研究期間をすごした群馬大学の山崎さんに参考になる話を聞いていたら， いつの間にかLA会誌にWGの報告を書かされることになりました(定理の正例です)． WGでは前回の「グラフマニアの世界」で紹介した問題に関する新しい情報もいくつか聞いてきたので， 最後に紹介したいと思います．
WGは正式名称は International Workshop on Graph-Theoretic Concepts in Computer Science と言います(今回が29回目でした)． グラフアルゴリズムが好きで好きでたまらない人がたくさん参加しています． 私は今回が2回目の参加だったのですが，2回とも非常に楽しかったです． 私から見た WG の印象は以下の通りです．
日本人が少なくて，かつ和やかな雰囲気なので，英語が苦手な私でも， 簡単に溶け込んで楽しむことができました．
なお，会費が安いのは，宿泊場所を工夫している点が大きいような気がします． 今回の開催地は Elspeet という町で，旅行会社の人も『聞いたことがないですね〜』と 言うくらいの，とても小さな町でした． まずアムステルダムから1時間くらい急行電車に乗り，Amersfoort という駅に行きます． つぎに鈍行に乗り換えて1時間くらい行き，そしてやっと Elspeet の隣町の Nunspeet につきます．Nunspeet駅で，すでに無人駅，駅前に店は1件，タクシーは電話をかけて呼ぶ， というレベルになってます． そして Nunspeet 駅前から乗り合いタクシーで30分くらい走ったところが Elspeet なのですが， そこからさらに森の中を10分くらい入ったところが会場でした． 日本で言えば「グリーンピアなんとか」とか，そういう感じです． 研究以外に，やることがありません．ネットワークもロクにつながらず，最高でした．
二日目の午後は貸切りバスで国立公園に連れて行ってもらって， 全員レンタルサイクルで森の中のサイクリングを楽しみました． 公園内には Kröller-Müller Museum という名前の美術館もあり， ゴッホの絵のコレクションが有名なところだそうです． おりしもゴッホ生誕150周年とかで，特別展をやっていました． さらに二日目の夜のバンケットでは何故かプロの手品師まで登場して， なかなか楽しい夜を過ごすことができました(右図)．
せっかくなのでオランダの印象も書いておきます． 一言でいえば「背が高い人が多い」ですね．どうしてなんでしょう？ カナダやアメリカは縦にも横にも大きい人がたくさんいますが， オランダはとにかく背が高い人が多いです． 町中ではたくさんの自転車を見たのですが， 私では到底足が届きそうもない自転車ばかりでした． 町は運河が多くて小奇麗なヨーロッパらしい町でした． 英語もおおむね通じるし，楽しいです．
アムステルダムにはその名もゴッホ美術館と言う，ゴッホ専門の美術館がありました． 群馬大学の山崎さんご推薦だったこともあり， せっかくなので行ってみると，おりしもゴッホ生誕150周年とかで，特別展をやっていました． ちなみにオランダにあるゴッホの絵のほとんどはゴッホ博物館と Kröller-Müller Museum に あるそうで，なんだか今回は得したような気がします． 私は美術にはほとんど興味がないのですが，今回のオランダではゴッホをたらふく満喫することができました． アーティストと研究者とは，共通点が多々あるような気がします． いわゆる破滅型とか放浪型には，ならないようにしなくては…．
アムステルダムの町をふらふら歩いていると「Hogeschool」というふざけた(?)名前の 看板を見つけて，思わず証拠写真(右図)を撮りました． 日本で UNIX を使っている人の多くは hoge という名前の作業ファイルを作ることが 多いような気がしているのですが，何か関係があるのかもしれません．…もちろんまったく関係ありません． Bodlaender 氏に聞いてみたところ，オランダでは high のことを hoge と言うそうです． 発音としては「ホッヘ」に近いようです．つまり Hogeschool とは高校のことであって， 別にふざけているわけではなかったようです．ちなみに丘とか丘陵地帯も hoge というそうです． そういえばWGの二日目に行った国立公園も De Hoge Veluwe という名前でした．
私の知っているオランダ語は以上です．もっと詳しいことは群馬大学の山崎さんに聞いて下さい．
前回のLAの会誌に，最近私が注目している二つのグラフクラスとして， probe interval graph と interval bigraph という二つのクラスを紹介したのですが， それぞれのその後を報告して，新たなネタを紹介したいと思います． 初めて読む方もいらっしゃると思うので，前回の原稿を再利用しつつ…．
これはバイオ系の人達によって導入されたグラフです． 以下の通り interval graph の自然な拡張になっています．
- 頂点集合は二つの集合PとNに分けられる
- 各頂点はある区間に対応する
- 2つの頂点I1,I2は，対応する区間が重なっていて， かつ少なくともどちらか一方がPに属する時に限って辺で結ぶ
N=φとすれば，普通のinterval graphになります． Pは Probe，NはNonprobe という意味なのですが，背景や文献は マニア本[BLS99,MM99,Spi03]や 最近の結果[JS01,MS02]を参照して下さい．
非常にいいかんげんなことを言えば probe interval graph は， interval graph と次に出てくる interval bigraph を足して2で割ったようなクラスです． Interval graph がかなり研究されているのと比較すると， これらのクラスはまだあまり研究されていません．
そんなわけでこのクラスについて，だいぶ力を注いだのですが，最近， やっと同型性が多項式時間で判定できることを示すことができました． この結果は今回のLAで発表するので，詳細はそこで，ということにしておきます．
これは interval graph の bipartite 版です．歴史は古く，1980年代初頭に
Harary, Kabell, McMorris らによって導入されました[HKM82]．
でもこのクラスが多項式時間で認識できることも1997年にやっと Müller氏
によって示された[Mul97]くらいで，詳しい性質はあまりわかっていませんでした．
そもそも，このクラスはなかなか手ごわいようで，
まず元の論文[HKM82]の特徴づけには間違いがあることが，
Müller氏の論文で指摘されています．
それからまた，そのMüller氏の論文にも間違いが見つかりまして，
Erratum が最近 Web で公開されました．
そして結局のところ彼の認識アルゴリズムの計算時間は
O(n5 m6
ところが今回の WG '03 で Müller氏にその後を聞いてみたところ， カナダの SFU の Hell 氏と Huang 氏が，非常に良い結果を出している，と教えてくれました． 早速ドラフト[HH03]を入手して読んだところ， 『補グラフを特徴付ける』という，コロンブスの卵的な手法で，非常に単純な特徴づけが与えられていました． 元のモデルがあまりにも自然なので『補グラフ』なんて考えたこともありませんでした．うむむ…． 彼らの特徴づけを利用すればおそらくはO(n2)， 悪くてもせいぜいO(n3)程度で判定できそうです．
さらに，前回の会誌では interval bigraph の同型性判定問題については未解決だ，とも 書いたのですが，上記の補グラフによる特徴づけを利用すると， interval bigraph の同型性判定問題は，多項式時間で解けることも，すぐわかります． もう少し正確に言うと，Hell 氏らの結果は，あるグラフが interval bigraph であることの必要十分条件は， そのグラフの補グラフが circular arc graph と呼ばれる別のクラスの subset に属していることである， というものです．Circular arc graph の同型性は多項式時間で判定できることが すでに知られている[Hsu95]ので， その subset についても，多項式時間で判定できることがすぐにわかります． 余談ですが，この circular arc graph というクラスも相当な曲者で， 線形時間の認識アルゴリズムが2001年のFOCSで発表されています[McC01]．
そんなわけで，probe interval graph についても interval bigraph についても， 一番おいしいところはもう既知の結果になってしまいました．
これだけで終わっては申し訳ないので，先日 Spinrad 氏に教えてもらった問題を紹介します． Spinrad 氏は最近，比較的読みやすいマニア本[Spi03]を出版しているのですが， その中にもちょっとだけ書いてあります．
これは interval graph と permutation graph を自然に拡張したグラフクラスです． 具体的には二つの平行線に挟まれた台形の集合によって定義される intersection グラフです． つまり各台形が各頂点に対応して，台形同士が共有部分を持つ時， 対応する頂点間にも辺がある，と定義されます．
Interval graph の同型性判定問題も permutation graph の同型性判定問題も， かなり昔に多項式時間アルゴリズムが示されている [LB79,CB81,Spi85]のですが， trapezoid graph については，まったくわかっていません． Spinrad 氏の言うところによると『多分多項式時間で判定できると思う』んだそうです． う〜ん，どなたか興味のある方，一緒に考えてみましょう．
そういえば WG '03 で私が何を発表したかを宣伝するのを忘れていました． ``Tree Spanners for Bipartite Graphs and Probe Interval Graphs''というタイトルで， マニア本[BLS99]の著者でもある Brandstädt 氏やLe氏， それからもう一人の Le 氏とDragan 氏との共著です[BDLLU03]． なぜ彼らと共同研究することになったのか，というと， 2002年の11月に Vancouver で開催された ISAAC がきっかけでした． 私はこの会議に参加(だけ:-)していたのですが，そのときに Dragan 氏が Tree Spanner について発表していて，その発表を聞いて， 彼と議論したことがきっかけになったものです． 国際会議に出ると，いいことがある，という定理の正例になってますね． 内容は夏のLAで報告済みなのですべて省略します． (蛇足のおまけ: 最近Brandstädt氏がかのErdős氏と かなり近い人だったことに気づきました．私もErdős数が3になりました:-)．
[BDLLU03] A. Brandstädt, F.F. Dragan, H.-O. Le, V.B. Le, and R. Uehara. Tree Spanners for Bipartite Graphs and Probe Interval Graphs. In 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '03), pages 106--118. Lecture Notes in Computer Science Vol. 2880, Springer-Verlag, 2003.
[BLS99] A. Brandstädt, V.B. Le, and J.P. Spinrad. Graph Classes: A Survey. SIAM, 1999.
[CB81] C.J. Colbourn and K.S. Booth. Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs. SIAM Journal on Computing, 10(1):203--225, 1981.
[HH03] P. Hell and J. Huang. Interval Bigraphs and Circular Arc Graphs. J. of Graph Theory, to appear. available at http://www.cs.sfu.ca/~pavol/intBig.ps.
[HKM82] F. Harary, J.A. Kabell, and F.R. McMorris. Bipartite intersection graphs. Comment. Math. Univ. Carolin., 23:739--745, 1982.
[Hsu95] W.-L. Hsu. O(M・N) Algorithms for the Recognition and Isomorphism Problem on Circular-Arc Graphs. SIAM Journal on Computing, 24(3):411--439, 1995.
[JS01] J.L. Johnson and J.P. Spinrad. A Polynomial Time Recognition Algorithm for Probe Interval Graphs. In Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 477--486. ACM, 2001.
[LB79] G.S. Lueker and K.S. Booth. A Linear Time Algorithm for Deciding Interval Graph Isomorphism. Journal of the ACM, 26(2):183--195, 1979.
[McC01] R.M. McConnell. Linear Time Recognition of Circular-arc Graphs. In Proc. 42nd Symp. on Foundations of Computer Science, pages 386--394. IEEE, 2001.
[MM99] T.A. McKee and F.R. McMorris. Topics in Intersection Graph Theory. SIAM, 1999.
[MS02] R.M. McConnell and J.P. Spinrad. Construction of Probe Interval Models. In Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 866--875. ACM, 2002.
[Mul97] H. Müller. Recognizing Interval Digraphs and Interval Bigraphs in Polynomial Time. Disc. Appl. Math., 78:189--205, 1997. Erratum is available at http://www.comp.leeds.ac.uk/hm/pub/node1.html.
[Spi85] J. Spinrad. On Comparability and Permutation Graphs. SIAM Journal on Computing, 14(3):658--670, 1985.
[Spi03] J.P. Spinrad. Efficient Graph Representations. American Mathematical Society, 2003.
|
Last modified: Tue Mar 18 11:35:50 JST 2008
by R.Uehara (uehara@jaist.ac.jp) |
|