著者

三溝 和明 朝廣 雄一 宮野 英次

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.4, pp.1-8, 2010-02-26

参考文献数

15

---

本稿では直径 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 部グラフといった制限された入力に対する近似可能性と近似困難性について考察する.The maximum diameter-bounded subgraph problem (MaxDBS for short) is defined as follows: Given an n-vertex graph G and a fixed integer d ? 1, we are asked to find the largest subgraph of the diameter d in G. If d = 1, the problem is identical to the well known maximum clique problem and thus it is NP-hard to approximate MaxDBS to within a factor of n1-ε for any ε > 0. Also, it is known to be NP-hard to approximate MaxDBS to within a factor of n1/3-ε for any ε > 0 and a fixed d ? 2. In this paper, we first strengthen this hardness result; we prove that, for any ε > 0 and a fixed d ? 2, it is NP-hard to approximate MaxDBS to within a factor of n1/2-ε. Then, we show that a simple polynomial-time algorithm achieves an approximation ratio of n1/2 for any even d ? 2, and an approximation ratio of n2/3 for any odd d ? 3. Furthermore, the (in)tractability and the (in)approximability of MaxDBS on subclasses of graphs are discussed for chordal graphs, split graphs, interval graphs, and k-partite graphs.