prueba de NP-completo del problema Dasgupta de Kite

Question

Estoy tratando de entender este problema desde Algoritmos. por S. Dasgupta, C.H. Papadimitriou, y de U.V. Vazirani, Capítulo8 , Pg281. Problema 8.19

A cometa es un gráfico en un número par de vértices, digamos $ 2n $, en la que n $ $ de los vértices forman un clique y los restantes $ n $ vértices están conectados en una “cola” que consiste en una ruta de acceso unido a una de las vértices de la camarilla. Dado un grafo $ G $ y una meta $ g $, el problema KITE pide un subgrafo que es una cometa y que contiene 2 g $ $ nodos. Demostrar que cometa es NP-completo.

Cualquier indicador que comienzan con este problema? Estoy completamente perdido con ella.

Answer 1

Se puede reducir la camarilla ($ G $ tiene una camarilla de tamaño $ k $) a Kite: dado $ G = (V, E) $ y $ k $, simplemente la acumulación en el tiempo polinomio de un nuevo gráfico $ G '$ de esta manera: para cada nodo $ $ v_i añadir una cola de $ k $ nuevos nodos

.

Si $ G '$ tiene una cometa de tamaño $ 2k $ entonces los $ G $ tiene un clique de tamaño $ k $ (la cometa sin la cola). Añadido nodos no pueden introducir nuevas camarillas en G ', por lo que $ G $ contiene exactamente las mismas camarillas de $ G' $.