擬似独立性を持つフィードバック点集合問題の提唱とアルゴリズムの開発

提出伪独立的反馈点集问题并开发算法

基本信息

批准号：
20J11259
负责人：
田村祐馬
金额：
$ 1.09万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-24 至 2022-03-31
项目状态：
已结题

项目摘要

当該年度は初めに，擬似独立性を持つフィードバック点集合問題の中で最も基礎的な「フィードバック独立点集合問題」の研究に取り組んだ．その結果，本問題の入力が平面二部グラフであったとしても，近似解の導出は非常に難しいことを証明した．その一方で，最大次数が小さい二部グラフに対して高速な近似アルゴリズムを与えた．これら成果を論文としてまとめ，国際会議「The 14th International Conference and Workshop on Algorithms and Computation (WALCOM2020)」にて発表した結果，Best Student Paper Awardを受賞した．また，証明を補完した学術誌版は「Theoretical Computer Science」にて掲載された．続いて，前述の結果の拡張を目的として「分割最小化問題」を提唱し，問題の計算複雑性の解析に取り組んだ．この「分割最小化問題」は，上記で述べた「フィードバック独立点集合問題」のみならず，研究課題に挙げた「擬似独立性を持つフィードバック点集合問題」，さらに理論計算機科学分野における様々な古典的問題の一般化となっている．本問題に対して，近似解の導出が困難となる十分条件を与えた．その一方で，FPTアルゴリズムという，最適解のサイズが小さいとき高速に動作するアルゴリズムを与えた．問題が特定の条件を満たしていれば困難性やアルゴリズムの結果が導けるという意味で，これらは多様な問題に対する計算複雑性を一度に与えた汎用的な結果となっている．これら成果を論文としてまとめ，国際会議「The 31st International Symposium on Algorithms and Computation (ISAAC2020)」にて発表した．また，学術誌には論文構成を推敲した後，投稿する予定でいる．

在第一年，我们首先研究了与伪独立的反馈点收集问题中最基本的反馈独立点收集问题。结果，即使该问题的输入是两个部分图，也证明了近似解决方案的推导非常困难。另一方面，将高速近似算法提供给具有最大数字较小的两个部分图。最好的学生论文被授予论文，并在国际会议上发表了“第14届国际国际会议和算法和计算研讨会（WALCOM2020）”。补充证明的学术期刊在“理论计算机科学”中发表。随后，我们提倡“最小划分矿山”，以扩大上述结果，并对问题的复杂性进行分析。如上所述，这种“最小化问题”不仅是上述“反馈独立点收集问题”，而且是“伪独立的反馈点收集问题”，如研究主题所述，以及理论计算器领域的各种经典作品这是问题的概括。这个问题给出了足够的条件，很难得出近似解决方案。另一方面，它给出了一种算法，该算法在最佳尺寸很小时以高速运行，称为FPT算法。这些是一个普遍的结果，即在问题满足特定条件和算法的结果的意义上，为各种问题提供计算和复杂性。结果是作为论文编辑的，并在国际会议上发表了“第31届国际算法和计算国际研讨会（ISAAC2020）”。此外，学术杂志将在详细阐述论文配置后发布。