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困難性を示すための一般的な定理も与え，弦グラフなどに対する困難性がそこから導かれることも示した．

我们通过图形结构参数创建的详细计算层次结构研究了算法设计和计算分析，并实现了以下结果。 - 我们提出了一种算法元定理，该定理统一并概括了到目前为止获得的一些顶点完整性算法。著名的算法Metatheromer（Courcelle的定理）使用树木宽度可以用一阶二阶逻辑编写的问题是Courselle的定理，但是这个结果将范围从树宽度图表到顶点完整性限制的图形范围缩小了感兴趣的范围，同时显着扩展了可以解决这些问题的问题。这也表明，可以使用该算法元定理解决各种问题。特别是，首先表明有缺陷的着色问题和各种最小联盟发现问题具有基于顶点完整性的FPT算法。 - 我们对组合过渡问题的图形结构参数进行了研究，结果，我们提出了一种算法元理论，该算法一次解决了各种问题。再次，我们使用了一层二阶逻辑，并提供了有关图形结构参数，邻域多样性的结果。它还展示了有关树深的算法元理论，并显示了对其概括限制的困难。 - 引入了定向图上的独立集滑动问题，以阐明各种情况下的计算复杂性。特别是，我们已经表明，可以在多项式时间内解决树木定向的图。 - 我们研究了图形上令牌的顺序交换，并提供了一个一般解决方案，其中包括所有先前已知的多项式时间溶解性。我们还提供了一个通用定理来显示NP难度，表明和弦图和其他因素的困难可以从中得出。

项目成果

期刊论文数量（35）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion

DOI：
10.1007/s00224-022-10076-x
发表时间：
2020-12
期刊：
Theory of Computing Systems
影响因子：
0.5
作者：
Yuuki Aoike;Tatsuya Gima;T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi
通讯作者：
Yuuki Aoike;Tatsuya Gima;T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi

Reconfiguration of Regular Induced Subgraphs

正则诱导子图的重新配置

DOI：
10.1007/978-3-030-96731-4_4
发表时间：
2022
期刊：
Lecture Notes in Computer Science
影响因子：
0
作者：
Eto Hiroshi;Ito Takehiro;Kobayashi Yasuaki;Otachi Yota;Wasa Kunihiro
通讯作者：
Wasa Kunihiro

Parameterized Complexity of Graph Burning

DOI：
10.1007/s00453-022-00962-8
发表时间：
2020-07
期刊：
Algorithmica
影响因子：
1.1
作者：
Yasuaki Kobayashi;Y. Otachi
通讯作者：
Yasuaki Kobayashi;Y. Otachi

Token Sliding on Split Graphs

代币在分割图上滑动

DOI：
10.1007/s00224-020-09967-8
发表时间：
2020
期刊：
Theory of Computing Systems
影响因子：
0.5
作者：
Belmonte Remy;Kim Eun Jung;Lampis Michael;Mitsou Valia;Otachi Yota;Sikora Florian
通讯作者：
Sikora Florian

Distributed Reconfiguration of Spanning Trees

生成树的分布式重构