Question

Je suis en train de comprendre ce problème Les algorithmes. par S. Dasgupta, C. H. Papadimitriou, et U.V Vazirani, chapitre8, Pg281. Problème 8,19

kite est un graphique sur un nombre pair de sommets, disons $ 2n $, où $ n $ des sommets forment une clique et le restant $ n $ sommets sont reliés en une « queue » qui se compose d'un chemin relié à l'un des Les sommets de la clique. Étant donné un graphe $ G $ et un objectif $ g $, le problème de KITE demande un sous-graphe qui est un cerf-volant et qui contient $ $ 2 g nœuds. Prouver que KITE est NP-complet.

Les pointeurs pour commencer à ce problème? Je suis complètement perdu avec elle.

Était-ce utile?

La solution

Vous pouvez réduire CLIQUE ($ G $ a une clique de taille $ k $) à KITE: donnée $ G = (V, E) $ et $ k $, juste construire en temps polynomial un nouveau graphe $ G 'de $ de cette façon: pour ajouter v_i $ chaque nœud $ queue de $ k $ de nouveaux nœuds

.

Si $ G '$ a un cerf-volant de taille 2k $ $, alors le G $ $ a une clique de taille $ k $ (le cerf-volant sans la queue). nœuds supplémentaires ne peuvent pas introduire de nouvelles cliques sur G ', donc $ G $ contient exactement les mêmes cliques de $ G' $.

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top