直径d部分グラフ最大化問題の計算複雑さ

• Item type: SIG Technical Reports(1)
• 公開日: 2009-02-26
• タイトル: 直径d部分グラフ最大化問題の計算複雑さ
• タイトル / 言語: en
• タイトル: Complexity of Max d-Diameter Subgraph Problems
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州工業大学大学院情報工学研究院
• 著者所属: 九州工業大学大学院情報工学研究院
• 著者所属: 九州産業大学情報科学部
• 著者所属(英): en
• 著者所属(英): Department of Systems Design and Informatics, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Systems Design and Informatics,Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Social Information Systems, Kyushu Sangyo University
• 著者名: 三溝, 和明; 宮野, 英次; 朝廣, 雄一
• 著者名(英): Kazuaki, Samizo; Eiji, Miyano; Yuichi, Asahiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，n頂点の連結無向グラフGと整数dが与えられたとき，直径がd 以下に限定され，頂点数が最大となるGの部分グラフを見つけることを目的とする直径d部分グラフ最大化問題(Max d-Diameter)を考える．d = 1 の場合は，本問題は最大クリーク問題と同一の問題である．本稿では，(i) 任意のε > 0およびd > 2 について，P = NP でなければ，Max d-Diameter に対して多項式時間で動作するO(n1-ε) 近似アルゴリズムは存在しないこと，および(ii) 入力を弦グラフに制限した場合にも，dが偶数の場合には，Max d-DiameterはNP困難となることを示す．また，(iii) dが奇数の場合には，弦グラフに対しても，Max d-DiameterはPとなり，(iv) 弦グラフの部分クラスである区間グラフに対しては，Max d-DiameterはPとなることを示す．さらに，(v) k > 2 について，k部グラフに対してMax d-DiameterはNP困難となることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The paper studies the maximum d-diameter subgraph problem (Max d-Diameter for short) which is defined as follows: Given an n-vertex graph and a positive integer d, the goal is to find its largest subgraph of a fixed diameter d. If d = 1, the problem is identical to the maximum clique problem. In this paper, we prove that (i) for all ε > 0 and d > 2, there is no polynomial time O(n1-ε) approximation algorithm for Max d-Diameter unless P = NP, and that (ii) for chordal graphs, Max d-Diameter is still NP-hard if d is even. We also prove, however, that (iii) if d is odd, then Max d-Diameter can be solved in polynomial time even for chordal graphs, and that (iv) it is in P for interval graphs, which is a subclass of chordal graphs. Furthermore, we show that (v) it is NP-hard for k-partite graphs of k > 2.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2009, 号 18(2009-AL-123), p. 65-72, 発行日 2009-02-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会