Requisito previo : Completitud de NP, Clase de NP, Gráfico disperso , Conjunto independiente
Problema: Dada la gráfica G = (V, E) y dos enteros a y b . Un conjunto de varios vértices de G tales que hay como máximo b aristas entre ellos se conoce como el subgrafo disperso del grafo G.
Explicación: el problema de subgráfico disperso se define de la siguiente manera:
- Entrada: Un gráfico no dirigido G = (V, E) y variables a , b .
- Salida: Un conjunto S que es un subconjunto de V donde | S| = a y hay como máximo b aristas entre pares de vértices en S . Informe «NO» , si no existe tal conjunto.
Para probar un problema NP Completo, hay dos pasos involucrados:
- Demostrar que el problema dado pertenece a la clase NP
- Todos los demás problemas de la clase NP pueden ser reducibles en tiempo polinomial a ese problema. (Esta es la prueba de ser NP-Hard)
Ahora bien, no es posible reducir cada problema NP a otro problema NP para probar su integridad NP todo el tiempo. Es por eso que mostramos que cualquier problema NP completo conocido es reducible a ese problema en tiempo polinomial.
Prueba:
1. El gráfico disperso pertenece a la clase NP:
Se dice que un problema está en la clase NP si la solución del problema se puede verificar en tiempo polinomial.
Dada una entrada G = (V, E) y dos variables enteras a y b.
- Para una solución dada S, toma O(|V|) tiempo para verificar que |S| =a.
- Para comprobar que el número de aristas entre cualquier par de vértices en S es como máximo b, necesitamos ejecutar el algoritmo O(|V| 2 ) .
Por lo tanto, la verificación de una solución para Sparse Graph toma como máximo O(|V| 2 ), que es de naturaleza polinomial, por lo que Sparse Graph pertenece a la clase NP.
2. Sparse Graph es un problema NP-Hard:
Ahora necesitamos mostrar que Sparse Graph es al menos tan difícil como un problema NP-Completo conocido mediante la técnica de reducción.
Aquí el problema conocido será el problema del conjunto independiente que ya se sabe que es NP-completo, que se explica en Prueba de que el conjunto independiente es NP-completo .
Vamos a mostrar la reducción de Conjunto independiente -> Gráfico disperso.
Conversión de entrada : necesitamos convertir la entrada del conjunto independiente a la entrada del gráfico disperso.
Entrada de conjunto independiente : un gráfico no dirigido G(V, E) y un número entero k.
Entrada de gráfico disperso : un gráfico no dirigido G'(V, E) y dos números enteros a y b.
Vamos a transformar la entrada de conjunto independiente a gráfico disperso de modo que
- G’ = G(V, E)
- un = k
- b = 0 ya que necesitamos tener el conjunto independiente máximo
Esta conversión tomará O(1) tiempo. Entonces es de naturaleza polinomial.
Conversión de salida : necesitamos convertir la solución de Sparse Graph a la solución del problema del conjunto independiente.
La solución del gráfico disperso dará como resultado un conjunto a que sería un conjunto independiente de tamaño k cuando k = a. Por lo tanto, la salida directa de Sparse Graph puede ser utilizada por Independent Set. Dado que no se requiere conversión, nuevamente es de naturaleza polinomial.
Corrección :
Implicación directa: considere cualquier conjunto independiente S. Este también es un gráfico disperso, ya que no hay bordes entre los vértices de S (b <= 0) y |S| = k = un
Implicación inversa: una solución de gráfico disperso dada S, también es un conjunto independiente (el número de aristas entre los vértices es cero, y |S| = k = a.
Entonces, esto significa que Sparse Graph tiene una solución ↔ Independent Set tiene una solución .
La reducción completa requiere un tiempo polinomial y el conjunto independiente es un problema NP completo. Entonces Sparse Graph también es un problema NP completo.
Conclusión:
Por lo tanto, podemos concluir que Sparse Graph es un problema NP Complete.
Para más detalles, consulte:
Diseño y Análisis de Algoritmos .