a prova NP-completo dal problema Dasgupta su Kite

Question

Sto cercando di capire questo problema da Algoritmi. da S. Dasgupta, C.H. Papadimitriou e U.V. Vazirani, Capitolo8 , Pg281. Problema 8.19

A aquilone è un grafico su un numero pari di vertici, diciamo $ 2n $, in cui $ n $ dei vertici formano una cricca e il restante $ n $ vertici sono collegati in una “coda” che consiste in un percorso unita ad una delle vertici dei cricca. Dato un grafo $ G $ e un obiettivo $ G $, il problema KITE chiede un sottografo che è un aquilone e che contiene $ 2g $ nodi. Dimostrare che KITE è NP-completo.

Tutti gli indicatori di iniziare con questo problema? Sono completamente perso con esso.

Answer 1

È possibile ridurre Clique ($ G $ ha una cricca di dimensioni $ k $) per KITE: dato $ G = (V, E) $ e $ k $, solo costruire in tempo polinomiale un nuovo grafico $ G '$ in questo modo: per ogni nodo $ v_i $ aggiungere una coda di $ k $ nuovi nodi

.

Se $ G '$ ha un aquilone di dimensioni $ 2k $ allora il $ G $ ha una cricca di dimensione $ k $ (l'aquilone senza coda). nodi aggiunti non possono introdurre nuove cricche su G ', in modo da $ G $ contiene esattamente gli stessi cricche di $ G' $.