クリーク問題の計算複雑度

最近計算量理論を独習する中で「クリーク問題」なるものを知りました。

<クリーク問題>
入力: グラフG、正整数k
質問: Gは大きさkのクリーク(完全グラフ)を含むか?

このクリーク問題の計算複雑度はNP完全とのことです。一方

<3クリーク問題>
入力: グラフG
質問: Gは大きさ3のクリークを含むか?

この3クリーク問題の計算複雑度はPとのことです。そして3に限らず(5とか100とか)任意の数の場合でやはり計算複雑度はPとのことです。(下記URL参照)

ここで疑問に思ったのですが、(PとNPは同一ではないという前提で)上の二つ(クリーク問題はNP完全、3クリーク問題はP)は矛盾してはいないでしょうか。すなわち、3クリーク問題、4クリーク問題、...がPで解けるのであればクリーク問題もPで解けるのでは、ということです。

どなたかこの件を解説していただけないでしょうか。
どうぞよろしくお願いいたします。

http://www.cs.bris.ac.uk/Teaching/Resources/COMS …
http://www.cs.bris.ac.uk/Teaching/Resources/COMS …

No.2 回答者： graphaffine 回答日時： 2009/10/29 19:31

先ほどの回答の後でよく考えてみたら、昔はクリークに関する問題で有名なものは最大クリーク問題だけでした。

従って、最大クリーク問題を単にクリーク問題と言っていたような気がします。
実際、私は質問者様が挙げた形のクリーク問題は知りませんでした。
AHOの本で言っているクリーク問題とは最大クリーク問題のことのような気がします。その本を持っていないので確認できませんが。

これだけでは何なので、下のサイトから状況証拠を。
http://www.ipsj.or.jp/katsudou/sig/kaikoku/MPS42 …

ここには、ある研究会の発表タイトル一覧にがありますが、その中に、以下の内容があります。
[クリーク問題と応用]
（42-１１） 15:30-16:00
Title: 最大クリーク抽出アルゴリズムの実験的評価

この回答へのお礼

再度の御投稿をありがとうございます。

No.1への補足で挙げました「アルゴリズムの設計と解析II」(1977年発行。元本は1974年発行)ではクリーク問題は「グラフGと整数kが与えられたとき、Gがk-クリークを含むか」という問題と定義されています。
ちなみに、1979年に発行された「Computers and Intractability」(Garey, Johonson著)という本(歴史的名著らしいですが)でもクリーク問題は「入力:グラフG=(V,E)、正整数k<=|V|; 質問:Gは大きさk以上のクリークを含むか?」と定義され、それとは別に最大クリークサイズ問題が「入力:グラフG、正整数k; 質問:G中の最大クリークの大きさは正確にkであるか?」と定義されています。
----
ですが、昔は最大クリーク問題のことをクリーク問題と言っていたかどうかには私自身はそれほど関心がなく(すみません)、質問に書いた定義に基づいてこの問題について教えていただければと思っております。
どうぞよろしくお願いいたします。

お礼日時：2009/10/29 20:13

No.1 回答者： graphaffine 回答日時： 2009/10/29 10:54

英語は弱いので、参考のPDFはおいといて回答します。

>このクリーク問題の計算複雑度はNP完全とのことです。

ただのクリーク問題と最大クリーク問題がごっちゃにされてるような。
NP完全は後者のことでしょ。

ご質問でのクリーク問題は、3クリーク問題、4クリーク問題、..を一般化させたkクリーク問題ですよね。本質は変わらないと思います。

最大クリークは、下記参照。
http://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7% …

この回答への補足

御投稿ありがとうございます。

>ただのクリーク問題と最大クリーク問題がごっちゃにされてるような。
>NP完全は後者のことでしょ。

「アルゴリズムの設計と解析II」(エイホ他著、サイエンス社)という本の143,144,153ページに「クリーク問題はNP完全」とあり、ネット検索で見つかるいろいろな大学の講義資料でも「クリーク問題(kクリーク問題)はNP完全」と書かれているのですが、それらは誤りということでしょうか。

>本質は変わらないと思います。

クリーク問題(kクリーク問題)はPに属する問題ということでしょうか。

御教示どうぞよろしくお願いいたします。

補足日時：2009/10/29 13:03

この回答へのお礼

どうやら以下のようなことのようです。
--------
たとえば

<3クリーク問題>
入力: グラフG=(V, E)
質問: Gは大きさ3のクリークを含むか?

はGの頂点数をnとしてO(n^3)で判定できる。しかし、

<クリーク問題>
入力: グラフG、正整数k
質問: Gは大きさkのクリーク(完全グラフ)を含むか?

についてはcをある定数としてO(n^c)で判定できるようなアルゴリズムはまだ見つかっていない。なので現在のところクラスPに属するとは言えない。(しかし、「証明」が与えられたときにその正しさをnの多項式時間で検証できるので、クラスNPには属する)

--------
貴重なお時間を費やして考えてくださった皆様、どうもありがとうございました。

お礼日時：2010/04/08 09:05