グラフ上の辺素パスに関する最適化問題の研究

本年度の研究の主な成果は,以下の3点に分類される.(1)点素パスに関する最適化問題点素(辺素)パスに関する最適化問題は,これまで自明なケース以外には多項式時間アルゴリズムが知られていなかったが,2008年にColin de Verdiere & Schrijverによって非自明なケースに対する多項式時間アルゴリズムが与えられた.そこで本年度の研究では,彼らの結果を他のケースに拡張し,平面グラフ上の問題で頂点対の数が少ないときの多くの非自明なケースに対するアルゴリズムを構築した.(2)辺素パス問題のアルゴリズム辺素(点素)パス問題に対しては,Robertson & Seymourによる多項式時間解法が知られているが,その正当性の証明は非常に難解であり,一般化した問題を扱う際の大きな障害となっている.また,彼らのアルゴリズムには,計算時間の中に頂点対数に依存した非常に大きな係数がかかってくる,という問題点がある.そこで本研究では,グラフに4辺連結性やオイラー性を仮定して,辺素パス問題に対するより単純で高速なアルゴリズムを与えた.(3)マトロイド構造を利用したアルゴリズムマトロイドの一般化として導入されたジャンプシステムや,その上で定義される離散凸関数は数多くの効率的に解ける組合せ最適化問題を含む枠組みである.本研究では,いくつかの具体的な組合せ最適化問題が,これらの構造の一般論を用いることで解けることを示した.特に,ジャンプシステムの理論を用いて,今まで多項式時間解法が知られていなかった(n-3)-連結度増大問題に対する初めての多項式時間解法を与えた.この成果は,個々の問題に対するアルゴリズムを構築する際に,ジャンプシステムや離散凸関数の理論が利用できることを明らかにしており,他の未解決の組合せ最適化問題に対する応用が期待される.

本年度の研究の主な成果は,以下の3点に分類される.(1)点素パスに関する最適化問題点素(辺素)パスに関する最適化問題は,これまで自明なケース以外には多項式時間アルゴリズムが知られていなかったが,2008年にColin de Verdiere & Schrijverによって非自明なケースに対する多項式時間アルゴリズムが与えられた.そこで本年度の研究では,彼らの結果を他のケースに拡張し,平面グラフ上の問題で頂点対の数が少ないときの多くの非自明なケースに対するアルゴリズムを構築した.(2)辺素パス問題のアルゴリズム辺素(点素)パス問題に対しては,Robertson & Seymourによる多項式時間解法が知られているが,その正当性の証明は非常に難解であり,一般化した問題を扱う際の大きな障害となっている.また,彼らのアルゴリズムには,計算時間の中に頂点対数に依存した非常に大きな係数がかかってくる,という問題点がある.そこで本研究では,グラフに4辺連結性やオイラー性を仮定して,辺素パス問題に対するより単純で高速なアルゴリズムを与えた.(3)マトロイド構造を利用したアルゴリズムマトロイドの一般化として導入されたジャンプシステムや,その上で定義される離散凸関数は数多くの効率的に解ける組合せ最適化問題を含む枠組みである.本研究では,いくつかの具体的な組合せ最適化問題が,これらの構造の一般論を用いることで解けることを示した.特に,ジャンプシステムの理論を用いて,今まで多項式時間解法が知られていなかった(n-3)-連結度増大問題に対する初めての多項式時間解法を与えた.この成果は,個々の問題に対するアルゴリズムを構築する際に,ジャンプシステムや離散凸関数の理論が利用できることを明らかにしており,他の未解決の組合せ最適化問題に対する応用が期待される.