Refining the graph parameter hierarchy for fine-grained algorithms

细化细粒度算法的图参数层次结构

基本信息

批准号：
21K11752
负责人：
大舘陽太
金额：
$ 2.66万
依托单位：
Nagoya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2026-03-31
项目状态：
未结题

项目摘要

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

我们通过详细描述由图结构参数创建的计算复杂度层次结构来研究算法设计和计算复杂度分析，主要得到以下结果。・我们提出了一个算法元定理，它统一并概括了迄今为止已获得的一些顶点完整性算法。使用树宽度来解决可由一元二阶逻辑描述的问题的算法元定理（库塞勒定理）是著名的，但虽然此结果将目标范围从树宽度受限图缩小到顶点完整性受限图，它大大扩展了可以处理的问题。我们还表明，使用这种算法元定理可以解决各种问题。特别是，首次证明了缺陷着色问题和各种最小联盟寻找问题具有基于顶点完整性的FPT算法。・我们对组合转移问题的图结构参数进行了研究，结果提出了一种可以同时解决各种问题的算法元定理。在这里，我们还使用了一元二阶逻辑，并显示了有关称为邻域多样性的图结构参数的结果。我们还提出了一个关于树深度的算法元定理，并展示了限制其泛化的困难。 -介绍了有向图上的独立集滑动问题，并阐明了各种情况下的计算复杂度。特别是，我们证明了对于具有有向树的图，这个问题可以在多项式时间内解决。・我们研究了图上代币的顺序交换问题，并提供了一个包含所有已知多项式时间可解性的通用解决方案。他还给出了一个证明 NP 难度的一般定理，并表明可以从中导出弦图的难度。