2015年度日本数学会賞春季賞

2015年度日本数学会賞春季賞

河原林健一(国立情報学研究所)
グラフマイナー理論とその計算量理論への応用に関する研究

河原林氏の研究は,グラフ理論を核とする離散数学とその理論計算機科学分野への応用まで,非常に多岐にわたる.またそれぞれの研究成果は,これまで未解決であった多くの問題に対し画期的なブレークスルーを与える,または解決にまで至るようなものばかりで,世界的に極めて高く評価されている.特に,グラフマイナー理論を高度に発展させ,アルゴリズム的な改良を推し進めた成果は,数学のみならず計算量理論上も画期的なものとして極めて高く評価されている. グラフマイナー理論は,RobertsonとSeymourらによる23編の論文によって証明された一連の研究で,現代グラフ理論の中核をなす.その骨格をなす定理の一つは,与えられたグラフ(例えばk頂点からなる完全グラフ)をマイナーとして含まないグラフの構造を記述する定理で,大雑把に述べると,特定の閉曲面にほぼ埋め込み可能であるような部分への分解と,それらを繋ぎ合わせる木構造とで記述される.この理論の動機づけとなっているのは,グラフ理論における最大の未解決問題であるHadwiger予想である.この予想は,与えられたグラフに含まれる完全マイナーと染色数との関係に言及したもので,平面グラフの四色定理を遙かに拡張した命題となっている.‘Kawarabayashi--Toftの6色定理’として知られる定理は,K7とK4,4をマイナーとして含まないグラフが6-彩色可能であることを証明したものであるが,Hadwiger予想に起因する問題でありながら,四色定理の証明とは異なり,コンピュータ計算を伴わない数学的な証明を与えたものとして高く評価されている.

また河原林氏は,アルゴリズム的グラフマイナー理論と呼ばれる理論を創始した.これは,グラフマイナー理論をアルゴリズムの観点から再構築するものであり,離散数学の各種の難問に多項式時間アルゴリズムを与え,計算量的に解決可能であることを示すものである.この理論のHadwiger予想への貢献として,Hadwiger予想には,四色定理の証明と同様に,有限時間で計算可能な証明または反例を与えるアルゴリズムが存在することを証明した. このように河原林氏は,理論計算機科学と数学の境界分野を開拓して,大きな学術分野を創設している.特筆すべきは,同氏の研究は,数学の成果を計算機科学に応用するだけでなく,理論計算機科学の知見から離散数学に光を与える双方向の効果を持つことである.加えて河原林氏は,2012年からJST(科学技術振興機構)ERATOの‘河原林巨大グラフプロジェクト’のリーダーとして,ネットワーク構造をもったビッグデータである‘巨大グラフ’を解析するための革新的なアルゴリズムの開発,およびそのための数学的理論を構築する研究を先導している.このプロジェクトは数学分野から初めての選出であり,日本における数学の発展に大きく寄与することは間違いない.

日本数学会
理事長 舟木 直久