Permítanme comenzar señalando que este es un problema de tarea, por favor brinden solo consejos y observaciones relacionadas, NO RESPUESTAS DIRECTAS por favor . Dicho esto, aquí está el problema que estoy viendo:
Deje HALF-CLIQUE = { | es un gráfico no dirigido que tiene una subgrafía completa con al menos nodos, donde n es el número de nodos en }. Muestre que HALF-CLIQUE es NP-complete.G n / 2 G
Además, sé lo siguiente:
- En términos de este problema, una camarilla se define como un subgrafo no dirigido del gráfico de entrada, en el que cada dos nodos están conectados por un borde. Una -clique es una camarilla que contiene nodos.
- De acuerdo con nuestro libro de texto, " Introducción a la teoría de la computación " de Michael Sipser , pg 268, que el problema CLIQUE = { | es un gráfico no dirigido con una -clique} está en NPG k
- Además, de acuerdo con la misma fuente (en la página 283), señala que CLIQUE está en NP-Completo (por lo tanto, obviamente, también en NP).
Creo que tengo el núcleo de una respuesta aquí, sin embargo, podría usar alguna indicación de lo que está mal o cualquier punto relacionado que pueda ser relevante para una respuesta . Esta es la idea general que tengo hasta ahora,
Ok, primero notaría que un certificado simplemente sería un HALF-QLIQUE de . Ahora parece que lo que tendría que hacer es crear un verificador que sea una reducción de tiempo polinómica de CLIQUE (que sabemos que es NP-Complete) a HALF-CLIQUE. Mi idea sería que esto se haría creando una máquina de Turing que ejecute el verificador de la máquina de Turing en el libro para CLIQUE con la restricción adicional para HALF-CLIQUE.
Esto me parece correcto, pero aún no confío en mí mismo en este tema. Una vez más, me gustaría recordarles a todos que este es un PROBLEMA DE LA TAREA, así que trate de evitar responder la pregunta. ¡Cualquier guía que no llegue a esto sería bienvenida!
fuente
El spoiler a continuación contiene una pista sobre cómo realizar esta reducción:
fuente
Puede reducir el problema de la cubierta del vértice. Si el gráfico del complemento del gráfico dado 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, es decir, será una media camarilla. Simplemente diga que es difícil resolver el problema de la cubierta de vértices, así es esto.
fuente