直径d部分グラフ最大化問題の近似について

概要

論文の詳細を見る
本稿では直径 d 部分グラフ最大化問題 (MaxDBS 問題) について考察する.MaxDBS 問題の目的は,入力グラフ G と整数 d?1 に対して,直径 d である最大部分グラフを G 中から見つけることである.MaxDBS 問題は,d=1 の場合,よく知られた最大クリーク問題と同一であるので,P≠NP の仮定の下で,任意のε>0 に対して n1-ε よりも良い近似度の近似アルゴリズムは存在しない.また d?2 に対しては,任意の ε>0 に対して n1/3-ε よりも良い近似度の近似アルゴリズムは存在しないことが知られていた.まず本稿では,この結果を改善し,任意の ε>0 に対して n1/2-ε よりも良い近似度の近似アルゴリズムは存在しないことを示す.また,d が偶数の場合には n1/2 -近似アルゴリズム,d が 3 以上の奇数の場合には n2/3 -近似アルゴリズムが存在することを示す.さらに,弦グラフ,スプリットグラフ,区間グラフ,k 部グラフといった制限された入力に対する近似可能性と近似困難性について考察する.
2010-02-26