权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

The following results were obtained from the study of structure design and computation hierarchy. This is a generalization of the theory of the vertex. The second order logic of single term describes the problem of the width of the tree and uses the theorem of the width of the tree to define the width of the tree. The solution of this problem is shown by the theorem. In particular, Defective color problems, such as the minimum loss of color problems, see the problem of vertex color problems, FPT loss of color problems, initial color problems, etc. The study of combinatorial migration problem is carried out in the paper. The results show that the combinatorial migration problem is solved in the paper. The second order logic of the single term is used in the middle, and the result of the near multiple property is shown in the middle. The depth of the tree is related to the difficulty of the generalization of the tree. The independent set design problem on directed design is introduced to explain the computational complexity of the situation. In particular, the problem is solved in polynomial time. The problem of successive commutations on the graph is studied, and the time solvability of polynomials is known. The difficulty of NP is shown in the general theorem and the difficulty of string is shown in the guide.

项目成果

期刊论文数量（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

Sequentially Swapping Tokens: Further on Graph Classes

顺序交换令牌：进一步了解图类

DOI：
10.1007/978-3-031-23101-8_15
发表时间：
2023
期刊：
Lecture Notes in Computer Science
影响因子：
0
作者：
Kiya Hironori;Okada Yuto;Ono Hirotaka;Otachi Yota
通讯作者：
Otachi Yota

Reconfiguring (non-spanning) arborescences

重新配置（非跨越）树状结构

DOI：
10.1016/j.tcs.2022.12.007
发表时间：
2023
期刊：
Theoretical Computer Science
影响因子：
1.1
作者：
Takehiro Ito;Yuni Iwamasa;Yasuaki Kobayashi;Yu Nakahata;Yota Otachi;Kunihiro Wasa
通讯作者：
Kunihiro Wasa

Algorithmic meta-theorems for combinatorial reconfiguration revisited

重新审视组合重构的算法元定理