MEDIO CLIQUE - NP problema completo

Question

Permítanme empezar señalando este es un problema de tarea, proporcione único consejo y observaciones relacionadas, RESPUESTAS NO DIRECTO favor . Dicho esto, aquí está el problema que estoy buscando en:

Let MEDIA camarilla = {$ \ langle G \ rangle $ | $ G $ es un grafo no dirigido que tiene una completa subgrafo con al menos $ n / 2 $ linfáticos, donde n es el número de nodos en $ G $ }. Muestran que la mitad-clique es NP-completo.

Además, sé lo siguiente:

• En términos de este problema un clique , se define como un subgrafo no dirigido de la gráfica de entrada, en el que cada dos nodos están conectados por un borde. Un $ k $ -clique es una camarilla que contiene $ k $ nodos.
• Según nuestro libro de texto, Michael Sipser de " Introducción a la Teoría de la computación ", página 268, que la camarilla problema = {$ \ langle G, K \ rangle $ | $ G $ es un grafo no dirigido con un $ k $ -clique} está en NP
• Además, según la misma fuente (en 283 pg) notas que CLIQUE está en NP-Complpete (por lo tanto también, obviamente, en NP).

Creo que tengo el núcleo de una respuesta aquí, sin embargo, que podría utilizar una idea de lo que está mal con ella o cualquiera de los puntos relacionados que pueden ser relevantes para una respuesta . Esta es la idea general que tengo hasta ahora,

Ok, me gustaría primera nota que un certificado sería simplemente una media de $ QLIQUE \ text {tamaño} \ geq n / 2 $. Ahora parece que lo que tendría que hacer es crear un verificador que es una transformación polinómica de camarilla (que sabemos es NP-completo) a la mitad de camarilla. Mi idea sería que esto se haría mediante la creación de una máquina de Turing que se ejecuta la máquina de Turing verificador en el libro de camarilla con la restricción adicional para Half-clique.

Este sonidos correctos para mí, pero realmente no confían en mí sin embargo, en este tema. Una vez más, me gustaría recordar a todos este es un problema de tarea así que por favor trate de evitar responder a la pregunta. La orientación que está a la altura de esto sería muy bienvenida!

Answer 1

A juzgar por su descripción y los comentarios, podría ser ayudado el mejor por una descripción exacta de cómo las reducciones se pueden utilizar para probar NP-completitud:

Un problema es NP-completo si y sólo si está en NP y es NP-duro. Esto significa que cualquier prueba de NP-completitud tiene dos partes: una prueba de que el problema está en NP y una prueba de que es NP-duro

.

En la primera parte, usted tiene que demostrar que YES-casos se pueden verificar en tiempo polinomial usando algún certificado adecuado. Como alternativa, puede mostrar el problema puede ser resuelto en tiempo polinómico por una máquina de Turing no determinista, pero esto no se hace por lo general como errores son fáciles de hacer.

En su caso, esto se reduce a demostrar que por cada gráfico con un $ n / 2 $ -clique, se puede encontrar alguna prueba de que efectivamente existe una camarilla de este tipo, de tal manera que, armado con tal prueba, se puede comprobar en tiempo polinómico que efectivamente existe tal una camarilla.

Para la segunda parte, usted tiene que demostrar que el problema es NP-duro. Esto es en casi todos los casos mostrados, demostrando que su problema es al menos tan duro como cualquier otro problema NP-duro. Si MEDIA clique es al menos tan duro como pandilla, también debe ser NP-duro.

Para ello, demostrando una reducción CLIQUE, A MEDIA camarilla. Usted 'reducir' el problema, por lo que es 'más fácil'. Usted dice "Solución clique es duro, pero me ha demostrado que sólo necesita para resolver MEDIA camarilla de resolver Clique". (Muchas personas, incluso los expertos, de vez en cuando dicen que esta al revés:))

Hay diferentes tipos de reducciones: la reducción que se utiliza con mayor frecuencia es en la que asigna los casos de camarilla en este caso a las instancias de MEDIA camarilla cuyo tamaño es como máximo polinómicamente más grande, en tiempo polinómico. Esto significa que si podemos resolver MEDIA pandilla, entonces podemos también resolver camarilla encadenando el algoritmo y la reducción.

En otras palabras, tenemos que demostrar que podemos resolver clique si podemos resolver MEDIA camarilla. Hacemos esto al mostrar que para cada instancia de pandilla, podemos diseñar una instancia de MEDIA camarilla de tal manera que la instancia de clique es un 'sí' ejemplo si y sólo si la instancia de Half-clique es un 'sí' instancia.

La prueba, por tanto, comienza así: dado un gráfico $ G = (V, E) $, I puede crear algunos gráfico $ H = (V 'E') $ tal que $ G $ contiene un $ $ k - clique iff $ H $ contiene un $ -clique $ n / 2. Voy a dejar esta parte de usted (esta es la parte que requiere creatividad, la parte que está sobre el problema específico que nos ocupa).

Answer 2

Se parece un poco perdido. ¿Quieres mostrar que la mitad camarilla $ \ ge $ pandilla, lo que significa que usted está buscando un algoritmo de tiempo poli que se lleva a instancias camarilla como los casos de entrada y salidas MEDIA camarilla con la propiedad de que "sí" entradas se asignan a " sí "es y "no" entradas se asignan a "no" s.

Así que, básicamente, la tarea es tomar un gráfico $ G $ y un número $ k $ y la salida de un nuevo gráfico $ H $ (y sin número) de manera que $ H $ tiene una camarilla en al menos la mitad de su vértices siempre $ G $ tiene una camarilla de tamaño $ k $.

El alerón siguiente contiene una pista sobre cómo llevar a cabo esta reducción:

Trate de hacer $ H $ uniendo (de alguna manera) una clique de tamaño apropiado a $ G $, además de algunos número de vértices no conectado a nada.

Answer 3

Se puede reducir el problema de cobertura de vértices. Si el gráfico de complemento de la gráfica dada tiene una cubierta de vértice inferior a n / 2 nodos entonces este gráfico tendrá una camarilla de más de n / 2 nodos que es que será una camarilla medio. Estado justo que es difícil de resolver el problema de manera Vertex Cover es esto.