Demostrar que Sparse Graph es NP-Complete

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 .

Publicación traducida automáticamente

Artículo escrito por surbhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *