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

点击翻译按钮获取中文摘要

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