グラフ最適化問題に対する高速高精度アルゴリズムの開発

本研究では，近似技法やパラメータ化技法による計算困難問題へのアルゴリズム設計，およびそれらの技法を組み合わせることにより既存アルゴリズムの限界を打破する高速高精度アルゴリズム設計スキームの基盤構築を行う．本年度は，主に計算困難なグラフ最適化問題に対する近似アルゴリズム，およびパラメータ化アルゴリズムなどの設計に取り組んだ．以下では結果を抜粋して詳細を述べる．(1)通常の最適化問題は解を1つ発見するような問題であるが，現実世界では複数の最適解を提示し，その中から適切な解を選ぶといった状況が考えられる．この際，似たような解を複数提示するのではなくある程度異なる解を提示する方が望ましい．このようなシチュエーションに対して，複数解の多様性を考慮した多様性最大化問題が提案された．本研究では，このようなタイプの問題に対する近似アルゴリズム設計フレームワークを構築した．このフレームワークに含まれる問題として，多様性最大マッチング問題， 多様性最大共通マトロイド問題，多様性最大最小カット問題などが挙げられる．本研究結果は人工知能分野のトップカンファレンスであるAAAI2023に採択された．(2)グラフの中から密な部分グラフを見つけることはグラフ探索の有効なアプローチの一つである．本研究では，k頂点部分グラフで最も密なものを探す最密k-部分グラフ問題に対して，各種グラフパラメータに関する固定パラメータ容易アルゴリズムを設計した．特に，グラフからp頂点削除するとクリーク幅が定数になるようなグラフに対して，O*(2^p)時間で動作するアルゴリズムを設計した．本研究によって，主要なグラフパラメータに関する最密k-部分グラフ問題のパラメータ化計算量が明らかになった．本研究結果は，Journal of Combinatorial Optimizationに採択された．

本研究では，近似技法やパラメータ化技法による計算困難問題へのアルゴリズム設計，およびそれらの技法を組み合わせることにより既存アルゴリズムの限界を打破する高速高精度アルゴリズム設計スキームの基盤構築を行う．本年度は，主に計算困難なグラフ最適化問題に対する近似アルゴリズム，およびパラメータ化アルゴリズムなどの設計に取り組んだ．以下では結果を抜粋して詳細を述べる．(1)通常の最適化問題は解を1つ発見するような問題であるが，現実世界では複数の最適解を提示し，その中から適切な解を選ぶといった状況が考えられる．この際，似たような解を複数提示するのではなくある程度異なる解を提示する方が望ましい．このようなシチュエーションに対して，複数解の多様性を考慮した多様性最大化問題が提案された．本研究では，このようなタイプの問題に対する近似アルゴリズム設計フレームワークを構築した．このフレームワークに含まれる問題として，多様性最大マッチング問題， 多様性最大共通マトロイド問題，多様性最大最小カット問題などが挙げられる．本研究結果は人工知能分野のトップカンファレンスであるAAAI2023に採択された．(2)グラフの中から密な部分グラフを見つけることはグラフ探索の有効なアプローチの一つである．本研究では，k頂点部分グラフで最も密なものを探す最密k-部分グラフ問題に対して，各種グラフパラメータに関する固定パラメータ容易アルゴリズムを設計した．特に，グラフからp頂点削除するとクリーク幅が定数になるようなグラフに対して，O*(2^p)時間で動作するアルゴリズムを設計した．本研究によって，主要なグラフパラメータに関する最密k-部分グラフ問題のパラメータ化計算量が明らかになった．本研究結果は，Journal of Combinatorial Optimizationに採択された．