CA-002
構造変化に応じるロバスト修復可能マトロイド基問題に対する固定パラメータアルゴリズム

伊藤健洋（東北大）・垣村尚徳（慶大）・神山直之（九大/JST）・小林佑輔（京大）・○岡本吉央（電通大）

本論文では，次のように定義する．新しいロバスト修復可能組合せ最適化問題の研究を行う．すなわち，ランクrのマトロイド M=(E, I) と E の部分集合 E₁, ..., E_s (ただし，各 E_i のランクは r )，自然数 k が与えられたとき，M の基 B で，各 i に対して，|B ∩ E_i| ≧ r - k を満たすものが存在するか答える問題を考える．これは E₁, ..., E_s という未来のシナリオに対して即座に対応できるような解 B を見つけるロバスト最適化問題であると捉えられる．本論文の結果は以下の通りである．まず，M が一様マトロイドまたはグラフ的マトロイドであっても，NP完全であることを示す．また，s をパラメータとしたとき，固定パラメータ・アルゴリズムを設計する．