⽥村 祐⾺
東北⼤学 ⼤学院情報科学研究科

グラフの頂点集合を，ある性質を持った部分集合に分割する問題を「グラフ分割問題」と呼ぶ．グラフ彩 ⾊問題を始め，多種多様な問題をグラフ分割問題とみなせることから，グラフ分割問題はグラフ理論の 分野において最も重要なトピックの1 つとなっている．さらに，近年ではグラフ分割問題の中でも「分割に おける特定の部分集合のサイズを最⼩化したい」という種類の問題が発展している．しかし，既存研究 の多くは性質を固定して進められており，性質に対する俯瞰的な研究は少なかった．
本研究では，上記のような既存の問題を統⼀的に扱うため「グラフ分割最⼩化問題」を提唱し，困難 性や容易性に関するフレームワークの構築を⽬的とした．初めに，遺伝的かつ加法的である⾮⾃明な 任意の性質について，本問題は多項式時間で近似解を求めることは難しいと証明した．本結果の系と して，既存の問題のいくつかについて平⾯⼆部グラフにおける近似困難性が導かれる．その⼀⽅で，性 質が特定の条件を満たす場合に，解サイズに関する固定パラメータアルゴリズムを与えた．さらに，性質 に「縮退数が定数」や「最⼤次数が1」といった条件が備わっている場合は，より⾼速なアルゴリズムが存 在することを⽰した．

この度は野⼝研究奨励賞という⼤変名誉ある賞をいただき，誠に光栄に思います．本研究をご指導い ただいた周暁先⽣，伊藤健洋先⽣，並びに，研究⽣活でお世話になった皆様に深くお礼申し上げま す．また，情報処理学会東北⽀部の皆様，及び選考委員の皆様に感謝いたします．本受賞を励み として，今後も情報処理分野に貢献できるよう，⼀層精進してまいります．