河原林健一氏の日本学士院学術奨励賞受賞に寄せて
徳山

豪

東北大学大学院情報科学研究科
河原林氏の日本学士院学術奨励賞（併せて日本学術振興会賞）受賞は非常に喜ばしいことであり，また，彼はそれにふさわしい研究者であると確信している．
河原林氏は，離散数学とその理論計算機科学への応用に関して，現在世界でも最高峰の若手研究者である．特に，彼が提唱しているアルゴリズム的グラフマイナー理論（AlgorithmicGraph Minor Theory）は世界を席巻している．この分野は数学会の会員諸氏にはあまりなじみがないかもしれないので，その意義や業績についてお話ししたいと思う．
河原林氏は慶応大学の博士課程でグラフ理論を学び，1 年間で博士の学位を 2001 年に取得した．その時の研究対象はグラフの部分構造に関するもので，特に，ハミルトン閉路の存在条件に関するロヴァース・ウッドウォール予想の解決に関する研究で日本数学会建部賞を受賞している．その後，グラフ理論の第一任者であるプリンストン大学のシーモア教授のもとで博士研究員を経験し，2003 年 8 月から 2 年半東北大学の情報科学研究科で助手，2006 年
より国立情報学研究所の准教授，2009 年より教授として勤務している．
初めて彼の業績を見る機会があった時のことを思い出すと，論文の数はもちろん，研究のセンスと質の良さは目を見張るものであった．これだけの人材を狭い分野に閉じ込めるのはもったいないというのが当時の印象である．
離散数学分野は，日本だと秋山仁先生やピーターフランクル，放浪の数学者エルデシュが有名で，少しアウトローのイメージがありがちだが，世界的には理論計算機科学や巨大データ解析との関係で非常に重要視されている分野である．アメリカ数学会の会長だったグラハ
ム，イスラエルの偉人アロン，京都賞をうけたクヌースやロヴァース，そして 2012 年のアーベル賞を受賞したセメレディなど傑出した研究者は，優れた数学者でありながら IBM やATT などの研究所と連携して，計算機科学の構築に積極的に取り組み，現代社会の発展に大きな貢献をもたらす科学者となって活躍している．私自身も数学から計算機科学に転向して成功したこともあり，ぜひ彼の数学の力を計算機科学に生かしてほしいと思った．これは結果的に日本の計算機科学や情報分野にとって非常に幸運であった．
河原林氏と直接話してみると，直感とアイデアが豊かで，またグラフに関する視野の広い理解と構想は期待以上のものであった．また，プリンストン大学で様々な研究者と触れ合っており，数学の情報科学への応用に非常に興味を持っていた．そこで，「義務は学生たちの飲み歩きに付き合うだけ（酒に関しては豪傑である）」ということで，大半は海外中心に研究交流に専念してもらうことにした．彼はそれほど社交上手には見えないのだが，明朗快活で親分肌であり，優秀な研究者とはすぐに仲良くなって共に成長する不思議な人徳を持っている．

実際天才と評判の高い MIT のドメイン氏を訪問した時に，短期間でアルゴリズム的グラフマイナー理論の最初の萌芽の成果をあげている．私自身は彼との共同研究はほとんどないのだが，環境整備に関しては自慢してもいいと思う．
閑話休題．河原林氏の業績について説明する．グラフは情報を表す構造として一般的かつ汎用的な離散構造であり，現実の世界の重要な問題は，ほとんどがグラフ上の「組合せ最適化」と呼ばれる問題として定式化される．したがって，グラフ上の組合せ最適化問題を効率的に解く効率的な手法は，情報関連の科学と産業にとって飛躍の鍵となる夢の技術である．
しかしながら，グラフ上の組合せ最適化問題はNP困難性という計算限界の壁を持ち，効率的な手法の指標とされる多項式時間アルゴリズムの設計は絶望的であるとされている．
一方で，特別なグラフ，例えば平面グラフでは多くの重要な組合せ最適化問題が効率的に解ける．代表的なものは，グラフ彩色，グラフ同形，最適描画問題などである．河原林氏のアルゴリズム的グラフマイナー理論は，これらのアルゴリズムの特徴を統一的な枠組みでとらえ，現実世界で使うほとんどのグラフ上に理論をひろげるものである．
少しだけ技術用語を説明すると，グラフGの頂点の削除と辺の削除及び縮退作業でグラフHが得られるときHをGのマイナーと呼ぶ．平面グラフは，K33及びK5を禁止マイナー（マイナーとして持てないグラフ）とするが，河原林氏の理論は一言でいうと，「平面グラフで解ける問題は，小さい禁止マイナーを持つグラフで解ける」という思想に基づいている．現実世界のグラフは小さい禁止マイナーを持つグラフに分解できることがほとんどであり，河原林氏は，そのような分解を実際行うアルゴリズムを開発し，そしてさらに各分解成分を処理することにより，今までNP困難性を乗り越えられなかったさまざまな問題を解決していっている．
これはまた，ロバートソンとシーモアらによって，四色問題及び理想グラフ予想という数学の大きな問題を解くために作られた，数十の論文からなる膨大な数学理論であるグラフマイナー理論の実用への転換でもある．河原林氏はまず数学的な成果として，例えば下記の成果をあげている
１． 六色定理（K7及びK44をマイナーに持たないグラフの六色彩色可能性）は，有名な四色問題の系列問題として，計算機による場合分けが不要な証明をもつ最初で唯一の定理である．
２． 任意のグラフに対して連結度に線形サイズの完全グラフマイナーが存在することを証明した．これは1980 年代より世界中の研究者が取り組んできた重要な予想であった．
３． 頂点数ｋの完全グラフをマイナーに持たないグラフはk－1色に彩色できるという四色問題を拡張した予想（ハドウィガー予想）に対して，四色問題と同様の計算機を用いた証明が可能であり，有限時間で証明が終わるアルゴリズムを示した．
これら数学に関する結果だけでも大変な重要性がある．そのほかにも離散数学分野で最も権威ある雑誌J. Combin. Theory Ser. Bに河原林氏の論文が約30本掲載されており，2000年代の掲載数の中で世界第１位である．
そして，これらの数学成果を強力な武器として理論計算機科学を先導しているのが，河原林氏の積極的かつ学際的なところである．いちいち紹介しきれないが，ホップクロフトとタルジャン（共にチューリング賞受賞者）による平面性判定や，平面グラフ同型判定アルゴリ
ズムの一般化，平面グラフのアルゴリズム設計で最も重要な概念であるセパレータ定理の一般化，曲面上へのグラフの非交差埋め込みや，埋め込まれたグラフ上のアルゴリズムなど，成果はそれぞれが重要な未解決問題や，専門家たちが夢見ていたような結果である．
それを如実に表しているのが彼に対する国際学会の評価である．理論計算機科学では，研究交流を重んじる伝統から国際会議が重んじられ，最高の国際会議での採択は論文誌採択よりもはるかに難しい．特に ACM Symposium on Theory of Computing（STOC），IEEEConference on Foundation on Computer Science（FOCS）は計算理論全般でもっとも格式が高く，また，ACM-SIAM Symposium on Algorithms and Discrete Algorithms（SODA）
は，アルゴリズム分野では最高の格付けがされ，最先端の研究者たちが論文のインパクトについて厳格なセレクションを行う．日本人研究者では，生涯に 1 つ論文が載ればかなり優秀で，複数の論文を持つ研究者は数えるほどしかいない．これに対して，3 つの国際会議を合せて採録数 30 本以上というのが彼の統計で，常識外のペースであり，日本どころか，MITやプリンストン等の研究者を抑えて，当該期間では世界最高である．つまり，世界中の研究者が著しく高く評価し，その動向を注目する存在であり，彼の新理論が過去に解けなかった難問を次々に攻略し，どんどん拡張している事を証明している．
河原林は国内外の学会での様々な活動にも積極的であり，非常に責任感の強い人物でもある．本年からは科学技術振興機構戦略的創造推進事業（ERATO）の実施者として，「巨大グラフ」をテーマに，数学と情報科学の融合の実用に向けて 6 年から 10 年の期間で年間数億円規模の大規模研究プロジェクトを走らせる．科学技術振興機構によると ERATO は「富士山型」（CREST は「八ヶ岳」さきがけは「牧場」）とされ，ERATO では実施者が全責任を持ち先導する．そういう面でも世界的にリーダーシップを持つ稀有の数学者であり，数学分野で長く待ち望まれた指導的研究者であると思う．
河原林氏は過去に日本 IBM 科学賞，文部科学賞若手科学賞，井上リサーチアワード，船井学術賞やカークマン賞，国際会議の論文賞など数多くの受賞も受け，また今回は日本学士院学術奨励賞を受けるわけだが，これらの受賞に甘んじずに，どんどん高みに登って行ってほしいというのが私の希望である．上記 ERATO など，今後どんどん責任は重たくなるとおもうが，そのプレッシャーを乗り越えて学会の将来を背負える人材であると信じている．数学会諸氏も，ぜひ今後ともバックアップをしていただきたく，よろしくお願いしたいと思う次第である．