Dominación sobre grafos

Descripción del problema

Los problemas de dominación en grafos constituyen una de las áreas más activas y versátiles dentro de la teoría de grafos, con una amplia gama de aplicaciones en diversas disciplinas. Esta familia de problemas se basa en la idea general de seleccionar un subconjunto de vértices que ejerza algún tipo de control o cobertura sobre el resto del grafo, considerando diferentes restricciones estructurales, operativas o relacionadas con costos. Este subconjunto de nodos se denomina Conjunto Dominante.

Contexto industrial

Esta familia de problemas tiene una fuerte motivación práctica. Por ejemplo, surgen en el diseño y operación de redes de comunicación, donde es necesario ubicar nodos de control, retransmisión o monitoreo de manera que toda la red quede adecuadamente cubierta. También son útiles para ubicar sensores en redes inalámbricas, en la planificación de servicios públicos (como estaciones de emergencia, centros logísticos o puntos de distribución), y en la difusión de información o influencia en redes sociales.

En el contexto de la influencia en redes sociales, diversos autores han abordado problemas de maximización de la influencia, cuyo objetivo es identificar el conjunto más pequeño de usuarios capaces de influir en el resto de la red a través de sus conexiones. Este objetivo está directamente relacionado con la búsqueda de conjuntos dominantes, ya que estos permiten alcanzar a todos los usuarios utilizando un modelo de difusión en cascada de un solo paso.

Desafíos comunes

• Minimum Dominating Set: Encontrar el subconjunto más pequeño de vértices tal que cada nodo del grafo esté en el subconjunto o sea adyacente a un nodo del mismo.
• Total Domination Set: Encontrar un subconjunto de vértices tal que cada nodo, incluidos los del subconjunto, tenga al menos un vecino en el conjunto. No se permite la autodominación.
• Independent Dominating Set: Encontrar un conjunto dominante que también sea un conjunto independiente, es decir, que no haya dos vértices adyacentes dentro del conjunto.
• Weighted Domination: Cada vértice tiene un costo o peso asociado. El objetivo es encontrar un conjunto dominante que minimice el peso total, no necesariamente el número de vértices.

Enfoques de solución

RedHEUR4.0 promueve el uso de algunas metaheurísticas para resolver problemas de dominación en grafos:

• Greedy Randomized Adaptive Search Procedure (GRASP)
• Variable Neighborhood Search (VNS)
• Iterated Greedy (IG)
• Scatter Search (SS)

Estas son herramientas eficaces para abordar problemas complejos de optimización combinatoria, en particular, problemas de dominación. En muchas situaciones del mundo real, las metaheurísticas ofrecen una alternativa eficiente capaz de proporcionar soluciones de alta calidad en tiempos de cómputo reducidos.

Referencias

1. Duarte, A. (2007). Metaheurísticas.
2. Propuesta RedHEUR4.0. (2022). Red Española de Optimización Heurística 4.0: Digitalización.
3. Wang, F. (2011). On positive influence dominating sets in social networks.

Agradecimientos

Con el apoyo del Ministerio de Ciencia e Innovación de España, este resumen refleja el trabajo en curso de la red RedHEUR4.0 en la promoción de la investigación sobre problemas de dominación en grafos y su papel en el desarrollo de técnicas avanzadas de optimización.