MEDIA CLIQUE - NP Completa el problema

20

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 GGGn/2G

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.kk
  • 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 kG,kGk
  • 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.sizen/2

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!

HermanoJack
fuente

Respuestas:

15

A juzgar por su descripción y comentarios, es posible que le ayude lo mejor una descripción exacta sobre cómo se pueden usar las reducciones para demostrar la integridad de NP:

Un problema es NP-complete si está en NP y es NP-hard. Esto significa que cualquier prueba de integridad de NP tiene dos partes: una prueba de que el problema radica en NP y una prueba de que es NP-hard.

Para la primera parte, debe demostrar que las instancias de SÍ pueden verificarse en tiempo polinómico usando algún certificado adecuado. Alternativamente, puede mostrar que el problema puede resolverse en tiempo polinómico mediante una máquina de Turing no determinista, pero esto no suele hacerse ya que los errores se cometen fácilmente.

En su caso, esto se reduce a probar que para cada gráfico con una camarilla , puede encontrar alguna prueba de que efectivamente existe una camarilla, de modo que, armado con tal prueba, puede verificar en tiempo polinómico que De hecho, hay una camarilla.n/2

Para la segunda parte, debes demostrar que el problema es NP-hard. Esto se muestra en casi todos los casos al demostrar que su problema es al menos tan difícil como algún otro problema NP-difícil. Si HALF-CLIQUE es tan duro como CLIQUE, también debe ser NP-hard.

Para ello, demostrando una reducción DE pandilla, A MEDIA camarilla. Usted 'reduce' el problema, haciéndolo 'más fácil'. Usted dice "Resolver CLIQUE es difícil, pero he demostrado que solo necesita resolver HALF-CLIQUE para resolver CLIQUE". (Muchas personas, incluso expertos, ocasionalmente dicen esto al revés :))

Existen diferentes tipos de reducciones: la reducción que se usa con mayor frecuencia es aquella en la que se asignan instancias de CLIQUE en este caso a instancias de HALF-CLIQUE cuyo tamaño es polinomialmente más grande, en el tiempo polinómico. Esto significa que si podemos resolver HALF-CLIQUE, entonces también podemos resolver CLIQUE encadenando el algoritmo y la reducción.

En otras palabras, debemos demostrar que podemos resolver CLIQUE si podemos resolver HALF-CLIQUE. Hacemos esto mostrando que para cada instancia de CLIQUE, podemos diseñar una instancia de HALF-CLIQUE de tal manera que la instancia de CLIQUE sea una instancia 'sí' si la instancia de HALF-CLIQUE es una instancia 'sí'.

G=(V,E)H=(V,E)GkHn/2

Alex ten Brink
fuente
Excelente configuración, creo que hizo un muy buen trabajo al proporcionar información suficiente para guiar sin proporcionar una respuesta y hacerlo de manera elocuente. Gracias.
BrotherJack
1
Algo así debería colocarse en la etiqueta wiki de np-complete para referencia futura. ¿Te importaría?
Raphael
8

GkHHGk

El spoiler a continuación contiene una pista sobre cómo realizar esta reducción:

HG

Louis
fuente
No entiendo lo que estás diciendo. Lo que intenté hacer fue reducir HALF-CLIQUE a CLIQUE modificando el varificador utilizado en el libro para demostrar que CLIQUE era NP, hacer que se ejecutara en el gráfico de entrada G, y si encontraba un CLIQUE verificando si dicho CLIQUE contenía al menos n / 2 nodos, donde n es el número de nodos en G. ¿No verificaría tal verificador de HALF-CLIQUE que el verificador de CLIQUE es una forma reducida de él (como en un subproblema de resolver HALF-CLIQUE )?
BrotherJack
¿O estás diciendo que lo tengo al revés y necesito demostrar que CLIQUE debe reducirse a HALF-CLIQUE? Tampoco estoy entendiendo tu spoiler. ¿Hay alguna forma de explicarlo sin dar la respuesta?
BrotherJack
3
Sí, para mostrar un problema es NP-completo, tiene que (a) muestra que está en NP y (b) reducir algunos conocido problema NP-duro para él. Para recordar la dirección correcta para la reducción, el punto es usar el nuevo problema como un "recuadro negro" para resolver eficientemente un problema conocido de NP-C.
Louis
OK, creo que lo entiendo ahora. ¡Gracias por tu ayuda!
BrotherJack
+1 Creo que lo tengo. Tu pista fue muy instructiva una vez que entendí lo que estaba haciendo mal. ¡Gracias de nuevo!
BrotherJack
0

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.

Arnav
fuente
1
Como puede reducir cualquier problema de NP completo, esto no es terriblemente útil. Se esperan detalles sobre la reducción.
Raphael
n/2