En el corazón del vasto océano azul, existe una isla tropical conocida como La Isla de Coba, un lugar de exuberante vegetación y antigua sabiduría. La tribu que habita en esta isla ha vivido en armonía con la naturaleza durante siglos, guiados por un consejo de ancianos que custodian el equilibrio entre los habitantes de la isla y sus recursos.
Sin embargo, una nueva generación de líderes debe ser elegida, y para ello, los ancianos han planteado un desafío ancestral. Los aspirantes al consejo deben descubrir un grupo selecto de guardianes, quienes, colocados en puntos estratégicos de la isla, podrían vigilar a todos los aldeanos sin dejar a ninguno sin supervisión directa o indirecta.
La isla tiene una serie de aldeas unidas entre ellas por caminos. El reto es encontrar un grupo de guardianes tan pequeño como sea posible, de modo que cada aldea esté bajo la protección directa de un guardián, o al menos, esté conectada a una aldea donde se haya asignado un guardián.
Los jóvenes líderes deben resolver este desafío para mostrar su valía. Con cada nueva selección de guardianes, la estabilidad de la isla se estremece. El futuro de La Isla de Coba depende de que uno de los jóvenes (como tú) encuentre esta distribución óptima de guardianes y se convierta en el próximo jefe absoluto.
Eliminando las particularidades del problema (aldeas, guardianes, etc.) tenemos que:
Dado un grafo
Al problema anterior se le denomina problema del conjunto dominante (dominating set problem), un problema
Formalmente, el conjunto dominante se define como:
Dado un grafo no dirigido
El número de dominancia de
El dominating set en un grafo con vértices aislados, los incluye por fuerza. Luego, el problema de computar el dominating set de un grafo con vértices aislados puede ser resuelto computando el dominating set del mismo grafo sin los nodos aislados y luego incorporando estos al resultado.
Por tanto, pasemos a demostrar que computar el dominating set de un grafo sin vértices aislados es NP-Hard.
Para ello, parece natural realizar una reducción desde Vertex Cover hasta Dominating Set, puesto que cada cubrimiento de un grafo sin nodos aislados es un dominating set de este; aunque no necesariamente el Minimum Dominating Set.
Mostremos que el problema de decisión de decidir si existe un dominating set de tamaño
El problema pertenece a NP, ya que una solución candidata puede ser verificada en tiempo polinomial, con tan solo computar el conjunto de vértices dominados y verificar que su tamaño sea igual al número total de vértices del grafo.
Ahora encontremos una reducción en tiempo polinomial desde el problema del Vertex Cover al problema del Dominating Set. Esto nos permitirá afirmar que Dominating Set es NP-Hard, con lo cual completaríamos la demostración de que es NP-Completo.
Para un grafo
Sea
Si
Si
Por otro lado, sea
Además, como para cada vértice
El algoritmo de conversión es meramente añadir un vértice y dos aristas por cada arista original, lo cual es polinómico.
Luego, como decidir si existe un Vertex Cover de tamaño
Para encontrar la solución exacta del problema del Conjunto Dominante, es necesario evaluar todas las combinaciones posibles de subconjuntos de vértices, lo cual puede tener una complejidad exponencial de
Se han desarrollado algoritmos que mejoran el tiempo de resolución exacta utilizando técnicas avanzadas de ramificación y poda, logrando reducir la complejidad a
Dado que encontrar la solución exacta es computacionalmente costoso para grafos grandes, los algoritmos de aproximación son una alternativa eficaz. Uno de los más comunes es el algoritmo greedy, que selecciona nodos de manera ávida, cubriendo en cada paso la mayor cantidad posible de nodos no cubiertos.
El algoritmo greedy no garantiza la solución óptima, pero ofrece una solución cercana en un tiempo razonable. La aproximación que ofrece está relacionada con el logaritmo del grado máximo (
Para obtener más detalles sobre la demostración de que el algoritmo greedy tiene una aproximación de
Demostración de la Aproximación del Algoritmo Greedy
A continuación se muestran los gráficos obtenidos tras la ejecución de los tests que comparan las soluciones exactas y aproximadas, así como el análisis del logaritmo del grado máximo.
Los gráficos muestran claramente las diferencias entre las soluciones obtenidas de manera exacta y las soluciones aproximadas mediante el algoritmo greedy. El análisis del logaritmo del grado máximo también proporciona información sobre la calidad de las aproximaciones obtenidas.