NP-Complete-Beweis aus dem Dasgupta-Problem auf Kite

Question

Ich versuche dieses Problem von zu verstehen Algorithmen. von S. Dasgupta, Ch Papadimitriou und UV Vazirani, Kapitel8, PG281. Problem 8.19

EIN Drachen ist ein Diagramm für eine gleichmäßige Anzahl von Scheitelpunkten, beispielsweise $ 2n $ Scheitelpunkte der Clique. Angesichts eines Diagramms $ G $ und eines Ziels $ G $ fragt das Kite -Problem nach einem Untergraphen, der ein Drachen ist und der $ 2G $ Knoten enthält. Beweisen Sie, dass Kite NP-Complete ist.

Gibt es Zeiger, mit diesem Problem zu beginnen? Ich bin völlig verloren.

Answer 1

Sie können Clique ($ g $ eine Clique mit Größe $ k $) auf Kite reduzieren: Zugegebener $ g = (v, e) $ und $ k $, bauen Sie einfach die Polynomzeit ein neues Diagramm $ g '$ auf diese Weise auf : Für jeden Knoten $ v_i $ fügen Sie einen Schwanz von $ k $ neuen Knoten hinzu.

Wenn $ g '$ einen Drachen mit 2.000 $ $ hat, dann hat der $ g $ eine Clique mit Größe $ k $ (der Drachen ohne Schwanz). Zusätzliche Knoten können keine neuen Cliquen auf G 'einführen, daher enthält $ g $ genau die gleichen Cliquen von $ g' $.