サイズ制約付き極小部分集合列挙問題に対する多項式遅延近似列挙アルゴリズムの研究

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

本研究では極小部分グラフ列挙において，極小性とサイズ制約を同時に扱う列挙問題に対し，効率良いアルゴリズムを開発することである．このような問題に対するこれまでのアプローチの一つとして拡張問題を解くというアプローチがあった．拡張問題とはある要素を含み，ある要素を含まない解が存在するかどうかを判定するYes/No問題であり，この問題を解くアルゴリズムと最適化，もしくは近似アルゴリズムを組み合わせることで小さな極小解を列挙することができる．しかし，近年の研究により，この拡張問題は大抵NP完全であることがわかってきた．そのため，このアプローチでの本研究で扱う問題を効率よく解くことは容易ではない．そこで，本研究ではもう一つの列挙アルゴリズムの構築技法である解グラフ技法に基づいたアプローチをおこなっている．このアプローチでは解同士に隣接関係を定義することでできた巨大な隣接関係のグラフを探索することで解を列挙する技法である．これまでの列挙アルゴリズムの構築において，この技法では定義されるグラフの強連結性にしか着目してこなかった．しかし，良い隣接関係を定義することで，小さい解と小さい解をつなぐ有向パスには小さな解しか含まれないように有向グラフを定義できることがわかった．この知見から，いくつかの列挙問題に対し，サイズ制約と極小性を近似的に満たしながら列挙するアルゴリズムを構築できることがわかった．さらに，今年度の研究において，極小な部分集合の列挙だけでなく，いくつかの極大な部分集合に関してもこのような有向グラフの定義ができることがわかった．証明の詳細にはなるが，今回の技法において極大で大きな解の列挙と極小で小さな解の列挙は大きく性質が異なる．そのため，極小解の列挙に使った技法は極大解については単純には適用できない．そのため，極大解に対してこのような技法を開発することも興味深い研究課題である．