KiteのDasgupta問題からのNP完全な証明

Question

私はこの問題を理解しようとしています アルゴリズム。 S. dasgupta、Ch Papadimitriou、およびUV Vazirani、第8章, 、PG281。問題8.19

a 凧 偶数の頂点のグラフであり、たとえば$ 2n $で、頂点の$ n $がクリークを形成し、残りの$ n $頂点は「テール」で接続されています。クリークの頂点。グラフ$ g $と目標$ g $を与えられた場合、カイトの問題は、カイトであり、$ 2G $ノードを含むサブグラフを要求します。 KiteがNP完全であることを証明します。

この問題から始めるポインターはありますか？私はそれで完全に迷子になります。

Answer 1

クリーク（$ g $にはサイズ$ k $のクリークがあります）をカイトに削減できます。 ：各ノード$ v_i $に対して、$ k $ newノードのテールを追加します。

$ g '$にサイズ$ 2k $のカイトがある場合、$ g $にはサイズ$ k $（尾のないカイト）のクリークがあります。追加されたノードはG 'に新しいクリークを導入できないため、$ g $には$ g' $のまったく同じクリークが含まれています。