Refining the graph parameter hierarchy for fine-grained algorithms

点击翻译按钮获取中文摘要

グラフ構造パラメータが作る計算量階層の詳細化によるアルゴリズム設計と計算量解析を研究し，主に以下の成果を得た．・これまでに得られている頂点インテグリティに対するアルゴリズムの一部を統一して一般化するアルゴリズム的メタ定理を示した．単項二階論理で記述できる問題に対する木幅を用いたアルゴリズム的メタ定理（Courcelleの定理）が有名だが，本結果は対象範囲を木幅限定グラフからから頂点インテグリティ限定グラフに狭める一方，扱える問題を大幅に広げるものである．また，様々な問題がこのアルゴリズム的メタ定理で解決できることも示した．特に，Defective彩色問題や，種々の最小アライアンス発見問題が頂点インテグリティによるFPTアルゴリズムをもつことを初めて示した．・組合せ遷移問題に対してグラフ構造パラメータに関する研究を行い，結果として様々問題を一度に解決するアルゴリズム的メタ定理を示した．ここでも単項二階論理を用い，近傍多様性というグラフ構造パラメータに関する結果を示した．また，木深度に関してもアルゴリズム的メタ定理を示すとともに，その一般化の限界を与える困難性も示した．・有向グラフ上での独立集合スライディング問題を導入し，様々な場合の計算量を解明した．特に，木を向きづけしたグラフに対してこの問題が多項式時間で解けることを示した．・グラフ上のトークンの逐次交換問題を研究し，これまでに知られていた多項式時間可解性をすべて含む一般的な解法を与えた．また，NP困難性を示すための一般的な定理も与え，弦グラフなどに対する困難性がそこから導かれることも示した．