Study on developing enumeration algorithms based on a supergraph technique

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

理論計算機科学における重要な問いとして，「実行可能解はいくつ存在するか」が挙げられる．この文脈において，解の個数を計数する問題と全ての解を実際に出力する問題の2つの観点で研究が進められているが，本研究では，後者を列挙問題と呼び，これに関して研究を行う．列挙問題は理論・応用両面において頻出する問題である．例えば，ユーザーが自身の嗜好を正確に定義できない場合，例えば夕食でどのレストランに行くか決める時などでは，ある程度候補となる対象を列挙し，その後実際にユーザーが目で見て自身の嗜好に適った対象を選ぶ，というような状況で列挙は重要な役割を果たす．このような状況では，効率良いアルゴリズムが提供されることは非常に重要である．これまで列挙アルゴリズムを構成するための様々なフレームワークやメタアルゴリズムが開発されてきたが，その適用範囲は限定されており，より汎用的な構築技法の確立が課題となっている．さらにそのようなフレームワークの適用限界についても全く明らかでない．本研究では，(1) スパース化を用いた解グラフ技法と呼ばれるフレームワークの拡張，および，(2) 局所的な構造に着目したメタアルゴリズムの開発を目的として研究を行う．令和4年度は，この内 (1) に注力した．その結果，k-辺連結全域グラフに関してアルゴリズムの開発が見込めそうだという結論に達した．これは2辺連結誘導グラフとは少し異なるが，このアイディアを応用して，2辺連結誘導グラフの列挙につなげて行く計画である．