Prerrequisitos: NP-Completo , Clase NP , Subgrafo denso
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 al menos b aristas entre ellos se conoce como subgrafo denso delgrafo G.
Explicación: Para probar el problema del subgrafo denso como NP-completo por generalización, vamos a probar que es una generalización del conocido problema NP-completo. En este caso, vamos a tomar a Clique como el problema conocido que ya se sabe que es NP-completo, y se explica en Prueba de que Clique es un NP-Completo y necesitamos mostrar la reducción de Clique → Subgrafo denso.
Clique es un subconjunto de vértices de un gráfico no dirigido tal que cada dos vértices distintos en el clique son adyacentes.
Prueba:
1. Conversión de entrada: necesitamos convertir la entrada de Clique a la entrada del Subgrafo denso.
Clique Input : un gráfico no dirigido G(V, E) y un entero k .
Entrada de subgrafo denso : un gráfico no dirigido G'(V, E) y dos enteros a y b .
Vamos a transformar la entrada de Clique para Dense Subgraph de modo que
- G’ = G(V, E)
- un = k
- b = (k * (k – 1))/2
Esta conversión tomará un tiempo O (1) , por lo que es de naturaleza polinomial.
2. Conversión de salida: necesitamos convertir la solución de Dense Graph a la solución del problema Clique.
La solución del gráfico denso dará como resultado un conjunto a que sería un Clique de tamaño k como k = a . Por lo tanto, Clique puede utilizar la salida directa de Dense Graph. Dado que no se requiere conversión , nuevamente es de naturaleza polinomial .
3. Corrección: Hemos restringido el rango del valor de entrada b tal que (k¦2) con valor como (k * (k – 1))/2 .
Ahora estamos buscando un subgrafo que tenga k vértices y que estén conectados por al menos (k * (k – 1))/2 aristas.
- Dado que en un grafo completo, n vértices pueden tener como máximo (n * (n – 1))/2 aristas entre ellos, entonces podemos decir que necesitamos encontrar un subgrafo de k vértices que tengan exactamente ( k * (k – 1) ))/2 aristas, lo que significa que el gráfico de salida debe tener una arista entre cada par de vértices que no es más que una camarilla de k vértices.
- De manera similar, un Clique de k vértices en un gráfico G(V, E) debe tener (k * (k – 1))/2 aristas que no es más que el subgrafo denso del gráfico G(V, E)
Bordes y vértices rojos denota un subgráfico denso con a = 4 y b = 5
Entonces, esto significa que Dense-Subgraph tiene una solución↔ Clique tiene una solución.
La reducción completa toma un tiempo polinomial y Clique es NP completo, por lo que Dense Subgraph también es NP completo.
Conclusión:
Por lo tanto, podemos concluir que Dense-Subgraph es NP Complete
Para más detalles, consulte:
Diseño y Análisis de Algoritmos .