The Independent Feedback Vertex Set Problem and Its Generalization

2021年8月15日 08:34

邦訳：グラフのフィードバック独立点集合問題とその一般化に関する研究

田村祐馬

（東北大学大学院情報科学研究科システム情報科学専攻　助教）

------------------ keyword ------------------
アルゴリズム
グラフ問題
計算複雑性解析
----------------------------------------------

【背景】グラフの点集合を分割しつつ，ある点集合を最小化する研究が発展
【問題】各研究は独立しており，俯瞰的な研究は少ない
【貢献】フレームワークを構築し，統一的に計算複雑性を解析

　点の集合と，2つの点同士を結ぶ辺の集合で表現されたデータ構造のことをグラフと呼ぶ．グラフは実社会における問題を抽象的に表現できることから広く研究が行われている．一例として会議室の予約を考えてみよう．各ユーザは会議室を使いたい時間を持っているとする．たとえば，Aさんは9:00～12:00の間，Bさんは10:00～15:00の間，といった具合である．このとき，AさんとBさんには別々の会議室を予約しなければならない．なぜならば，会議室を使いたい時間に被りがあるからである．一方で，使える会議室には限りがある． 3つの会議室だけを使用できるとき，すべてのユーザは会議室を予約できるだろうか？

　この問題はグラフ上の彩色問題として考えることができる．ユーザを点に置き換え，ユーザ間で使用時間に被りがあるとき，対応する点同士を辺で結ぶ．このようにして構成されたグラフに対し，頂点に色を割り当てる．ただし，同じ色の点同士は辺で結ばれてはならない．このような色の割り当てをグラフの彩色と呼び，各色はユーザが使う会議室に対応する．すなわち，前述の「3つの会議室をすべてのユーザーが予約できるか？」という問題を，「グラフを3色で彩色できるか？」という彩色問題として考えることができる．彩色問題として扱うことのできる実社会上の問題は会議室の予約だけではない．無線局の帯域割り当てや，世界地図の塗り分けなども彩色問題として考えることができる．

　さて，各ユーザは会議室を無事に予約できるとしよう．しかし実際には，設備保守等の理由により，ある会議室の使用はできるだけ控えたい状況があり得る．これはグラフ上の彩色で考えると，特定の色を持つ点の数を最小化することに対応する．では，グラフが与えられたとき，そのような彩色を見つけることはできるのだろうか？

　このような，グラフの点集合を「特定の性質」を持つ複数の部分集合に分割しつつ，ある部分集合のサイズを最小化したい，という問題の研究が近年になり発展している．しかし，個々の研究は「特定の性質」を1つ固定した上で進められており，「特定の性質」に対する俯瞰的な研究は少なかった．

　そこで，本研究ではこれら問題を「分割最小化問題」として統一し，「特定の性質」の観点から問題を解析した．もう少し具体的に述べると，最適とは限らない点集合の分割自体が仮に与えられたとしても，最適解に対する近似解（程よい解）すら見つけることは難しくなるような，「特定の性質」に対する十分条件を与えた．一方で，「特定の性質」によってはFPTアルゴリズムと呼ばれる，解のサイズが小さいときに高速に動作するアルゴリズムが存在することを示した．また，「分割最小化問題」の中でも基礎的な「フィードバック独立点集合問題」に着目し，グラフ構造に基づいた多項式時間アルゴリズム，多項式時間近似アルゴリズム，FPTアルゴリズムをそれぞれ与えた．

（2021年5月26日受付）
（2021年8月15日note公開）

ーーーーーーーーーーーーーーーーーー
　取得年月日：2021年3月
　学位種別：博士（情報科学）
　大学：東北大学
ーーーーーーーーーーーーーーーーーー

推薦文：（アルゴリズム研究会）
本論文ではグラフアルゴリズムの分野で基本的な多くの問題を統一的に扱う「分割最小化問題」を提唱し，計算複雑性の観点からさまざまな解析を行っている．本論文の内容は国際会議ISAACを始め3本の国際会議で発表済みであり，国際会議WALCOMではBest Student Paper Awardを受賞するなど，国際的に高く評価されている研究として推薦する．　

田村祐馬（正会員）

研究生活：私は修士課程を修了後，3年間非研究職に従事していました．しかし，元々は研究職志望というのもあって一念発起し，退職した上で博士課程に進みました．修士課程からそのまま博士課程に進むべきだった，という思いはことあるごとに頭の中を巡りますが，研究からいったん離れたことにより視野が広くなったと感じること，金銭面で多少は余裕が生まれたことを考えると，マイナスばかりではなかったように思います．研究室に戻ってからは修士時代の研究を発展させようと取り組み，苦労もありましたが，なんとか博士論文にまとめることができました．充実した研究室生活でしたが，新型コロナウイルスの影響により，昨年度は研究室メンバと対面で話す機会が極端に少なかったことが悔やまれます．

指導教員である周暁教授および伊藤健洋教授には学部生時代から大変お世話になり，同時に多くのご迷惑をお掛けしました．この場を借りてお礼申し上げます．