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

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

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

基本信息

批准号：
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)」にて発表した．また，学術誌には論文構成を推敲した後，投稿する予定でいる．

At the beginning of the year, the most fundamental of the quasi-independence problems is the independent point set problem. As a result, the approximate solution of this problem is very difficult to prove. The maximum number of times in one direction is small, and the maximum number of times in two parts is small. "The 14th International Conference and Workshop on Algorithms and Computation (WALCOM2020)" presented its results and won the Best Student Paper Award. The academic journal version of the proof was published in Theoretical Computer Science. In this paper, the aim of the above results is to propose the "partition minimization problem", and the solution of the computational complexity of the problem is divided into two groups. This "partition minimization problem" is opposite to the "independent point set problem" mentioned above. The research topic is "quasi-independence problem", which is a generalization of classical problems in theoretical computer science. This problem is difficult to derive approximate solution. In one direction, FPT is the most suitable solution for small and high speed operation. The problem is difficult to solve under certain conditions, and the result is computationally complex. The 31st International Symposium on Algorithms and Computation (ISAAC2020) The academic journal is composed of papers.