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

グラフの構造的パラメータに基づく汎用的アルゴリズムの構築

基于图结构参数的通用算法构建

基本信息

批准号：
21K21278
负责人：
田村祐馬
金额：
$ 1.66万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Research Activity Start-up
财政年份：
2021
资助国家：
日本
起止时间：
2021-08-30 至 2024-03-31
项目状态：
已结题

项目摘要

本研究では，一般的に解くことが困難であるグラフ上の組合せ最適化問題に対し，「mim-width」や「sim-width」といった，グラフの構造的パラメータを利用した効率的なアルゴリズムの構築を目標とした．本年度はmim-widthが1や2といった小さい値を取るグラフ上での，最大誘導部分グラフ問題を扱った．グラフアルゴリズム分野で扱われている様々な問題は，最大誘導部分グラフ問題またはその双対問題として扱うことができる．例えば，最大独立集合問題，最大クリーク問題，最大クラスター問題，及び最小頂点被覆問題，最小フィードバック頂点集合問題はその一例である．また，区間グラフ，置換グラフ，距離遺伝グラフ等といった，グラフ理論分野で古くから研究されているグラフの多くは，mim-widthが1ということが知られている．したがって，mim-widthが小さいグラフ上で最大誘導部分グラフ問題を考えることは，多様なグラフ上における多様な問題を一度に扱うことに繋がり，極めて重要な意味を持つ．令和4年度の本研究では，最大クリーク問題や最大クラスター問題といった密な誘導部分グラフを求める問題はmim-widthが2であってもNP困難，すなわち最適解を現実的な時間で求めるアルゴリズムは存在しそうにない，という定理を与えた．この定理は，特定の性質を持つ任意の問題に対して成り立つという意味で汎用的な結果を表している．一方で，mim-widthが1であるグラフに対しては，そのグラフの構造的特徴を利用して最大クリーク問題や最大クラスター問題を高速に解くアルゴリズムを構築した．また，これら問題を解く過程で得た手法が，他の問題にも応用可能であることを示した．したがって，mim-widthというグラフの構造的パラメータに着目することで，汎用的なアルゴリズムを構築できたと言える．

In this paper, the general problem of combinatorial optimization is solved, and the problem of "mim-width" and "sim-width" is solved. This year, the mim-width is 1 to 2, and the maximum induction part is 1 to 2. The problem of maximum induction is the problem of double pairs. For example, the maximum independent set problem, the maximum crisisproblem, the maximum crisisproblem, and the minimum vertex covering problem, the minimum crisisproblem. , interval The maximum induction part of the maximum induction part of the maximum induction part of In this study, the maximum problem and the maximum problem of the induced part are solved by mim-width and NP difficulty, and the optimal solution is solved by time. The theorem is that a particular property holds an arbitrary problem, and the result of the problem is expressed in general terms. On the one hand, mim-width is 1, and on the other hand, the characteristics of the structure of the structure The problem is solved in a way that can be explained. The structure of the mim-width of the mim-width of the mim