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

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

• 批准号: 21K21278
• 负责人: 田村 祐馬
• 金额: $ 1.66万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-08-30 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K21278/
• 关键词: グラフアルゴリズム; グラフパラメータ; 計算複雑性; 最大誘導部分グラフ問題; 最大幸福頂点集合問題; 区間グラフ; 置換グラフ

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

在这项研究中，我们将使用“mim-width”和“sim-width”等图的结构参数来开发有效的算法，以解决通常难以解决的图上的组合优化问题。今年，我们处理了图上的最大诱导子图问题，其中 mim-width 取较小的值，例如 1 和 2。图算法领域中处理的各种问题都可以视为最大诱导子图问题或其对偶问题。示例包括最大独立集问题、最大团问题、最大簇问题、最小顶点覆盖问题和最小反馈顶点集问题。此外，众所周知，图论领域长期研究的许多图，例如区间图、排列图、距离遗传图，其mim-width为1。因此，考虑mim宽度较小的图上的最大诱导子图问题非常重要，因为它允许我们同时处理各种图上的各种问题。在2020财年进行的这项研究中，我们发现，即使mim-width为2，需要密集引导子图的问题（例如最大团问题和最大簇问题）也是NP难的，即计算最优解的算法他给出了一个现实的时间量是不可能存在的定理。该定理代表了一般结果，因为它适用于具有特定属性的任何问题。另一方面，对于mim-width为1的图，我们构造了一种利用图的结构特征来快速解决最大团问题和最大簇问题的算法。我们还表明，在解决这些问题的过程中获得的方法可以应用于其他问题。因此，可以说，通过关注称为 mim-width 的图的结构参数，我们能够构建通用算法。

项目成果

Happy set problem on subclasses of co-comparability graphs

协同可比图子类的快乐集问题

• DOI: 10.1007/978-3-030-96731-4_13
• 发表时间: 2022
• 期刊: Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science
• 作者: Hiroshi Eto;Takehiro Ito;Eiji Miyano;Akira Suzuki;Yuma Tamura
• 通讯作者: Yuma Tamura

Parameterized complexity of optimizing list vertex-coloring through reconfiguration

通过重新配置优化列表顶点着色的参数化复杂度

• DOI: 10.1007/978-3-031-27051-2_24
• 发表时间: 2023
• 期刊: Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023), Lecture Notes in Computer Science (LNCS)
• 作者: Yusuke Yanagisawa;Akira Suzuki;Yuma Tamura and Xiao Zhou
• 通讯作者: Yuma Tamura and Xiao Zhou