Algorithms for graph problems with monadic second-order properties via structural graph parameters
2023年度研究会推薦博士論文速報
［アルゴリズム研究会］
儀間 達也
（北海道大学 大学院情報科学研究院 助教）
邦訳：グラフ構造パラメータと述語論理を用いた高速メタアルゴリズム
■キーワード
グラフアルゴリズム／計算複雑性／有限モデル理論
【背景】グラフ構造を利用したアルゴリズム高速化手法
【問題】個別の問題に対するアドホックな手法
【貢献】高速なアルゴリズムの自動生成
グラフは，頂点と，2つの頂点間の「関係」を表す辺の2種類で表現される構造です．その抽象性の高さと，計算機（コンピュータ）にとっての扱いやすさなどから，通信網，道路網，人間関係といった実世界の構造の数学的なモデルとして幅広く応用されています．そのため，グラフ上の組合せ最適化問題は，現実の多くの問題の基礎となる問題として研究が進んでいますが，その多くは一般にはNP困難という，高速に厳密解を計算することが非常に困難な問題です．たとえば，たくさんの人々と，各個人の嫌いな人が与えられたとき，どのチームも嫌い合う人のペアがいないように3チームを作る問題を考えてみます．この問題はグラフで解釈すると，3彩色問題と呼ばれている問題で，一般にはNP困難な問題です．
ところが，木というある意味最も疎なグラフや，その一般化である木幅というパラメータが小さなグラフでは，一般にNP困難な問題の多くが高速に解けることが知られています．特に有名なものとして，Courcelleの定理があります．これは，考えている問題が「単項二階述語（MSO）論理で記述」できるのであれば，木幅が小さなグラフに対して非常に高速なアルゴリズムを生成できることを示したものです．この定理1つによって，先ほど例示した3彩色問題を含む膨大な量のNP困難問題が，木幅が小さなグラフでは高速に解けることが分かってしまうため，その一般性の高さなどから，メタアルゴリズムとも呼ばれます．
その一方，MSO論理では表現できないような問題も数多く存在します．たとえば，先程の3彩色問題の例において，各チームの人数が等しいことも要求してみると，問題はとても難しくなります．この問題は公平3彩色問題と呼ばれ，MSO論理では表現できず，また木幅が小さなグラフでもある意味で高速に解くことが難しいと考えられています．そのような木幅が小さいグラフでも困難な問題に対して，頂点被覆数など，木幅よりも制限の強いパラメータを利用したアルゴリズム高速化の研究が盛んに行われていましたが，それぞれ個別の問題に対してアルゴリズムの設計が行われてきていました．そのようなアルゴリズムの多くを包括するような枠組みでアルゴリズムを与えたのが，本研究の成果の1つです．特に，公平3彩色問題などを扱えるような，頂点集合の大きさの比較などを表現可能なようにMSOを拡張した枠組みに含まれるすべての問題に対し，頂点インテグリティという値が小さなグラフでの高速なアルゴリズムを与えることができました．
また，組合せ遷移という問題群に対し，MSOを利用したアルゴリズムを与えました．古典的な計算機科学的問題の多くは，解を1つ探すか，解の個数を数えるようなものです．それに対し，組合せ遷移問題は，「解と解の連結性」を問う問題で，その多くは解を1つ見つけるよりも格段に解くのが難しくなる問題です．
本研究では，近傍多様性といったパラメータが小さなグラフにおいてMSOで表現できる組合せ遷移問題が効率的に解けることなどを示しました．
（2024年5月31日受付）
（2024年8月15日note公開）
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
取得年月：2024年3月
学位種別：博士（情報学）
大学：名古屋大学
正会員
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
推薦文［コンピュータサイエンス領域］アルゴリズム研究会
本研究では，グラフ構造パラメータをある種の述語論理と組み合せたアルゴリズム的メタ定理を複数与えている．これは，対象となる問題が決められたルールで記述できる場合に自動的に効率的アルゴリズムを与えるものであり，多くの問題を同時に解决するものである．グラフアルゴリズム理論への大きな貢献として推薦する．
研究生活 学部生のころは，研究として具体的に何かをやりたいという意識もなく，指導教員からいただいたテーマをやり遂げて卒業しました．修士に入ってから，そのテーマの源流にあった，Courcelleの定理などを知り，非常に興味が湧きました．もともと学部1年頃にHaskell（プログラミング言語）にはまった影響で，型理論や数理論理などをかじっていた時期もあったので，それを思い出しながら自分の興味関心の核はこの付近にあるのかもと感じました．
ところで，研究生活で最も大事だと感じたのは，体調管理です．修士入学時からコロナ禍が始まったこともあり，研究のほとんどは自宅で行いました．一人暮らしで自宅にこもると，食生活の偏りや，睡眠周期のズレ，運動不足，日光不足を招くことになり，思いの外パフォーマンスに大きく影響しました．研究は長期戦です．年単位でのパフォーマンスを考えると，健康的な生活をすることの優先度はものすごく高いと感じました．