Page 11 - Boletín CIMAT Marzo 2021

Figura 1. Gráfica con conjuntos independientes fuertes sombreados de amarillo. La figura 1a representa un conjunto independiente fuerte maximal. La figura 1b representa un conjunto independiente fuerte máximo.
Conelincrementodesistemasdecómputocada vez más poderosos, el estudio de algoritmos y complejidad es importante con el fin de diseñar algoritmos eficientes que permitan implementar sistemas de cómputo cuya ejecución sea óptima. Actualmente el reto se vuelve mayúsculo, ya que los sistemas de cómputo se encuentran distribuidos en ecosistemas cada vez más complejos.
El estudio de teoría de gráficas es importante en un gran número de disciplinas en matemáticas, ingenierías y en ciencias de la computación. Una gráfica consiste de un conjunto de objetos denominados nodos interconectados mediante aristas. En la figura 1 los círculos representan los nodos y las aristas se representan mediante las líneas que los unen.
El proyecto en cuestión se relaciona con el diseño de algoritmos para un problema particular en una gráfica. El problema del conjunto independiente fuerte (CIF) (en inglés denominado: 2-packing set) consiste encontrar el subconjunto de nodos de mayor carnalidad en una gráfica, que cumplan con la condición de que cualquier par de elementos de dicho conjunto, están a una distancia mayor a dos aristas. Como se muestra en la figura 1, los nodos en color amarillo representan un conjunto independiente fuerte.
Encontrar un conjunto independiente fuerte tiene aplicaciones interesantes en asignación de frecuencias, diseño de redes, entre otras. En la figura 1a se ilustra un CIF maximal (un conjunto al que no es posible añadir otro vértice al CIF) y en la figura 1b se ilustra un CIF máximo (un CIF maximal de cardinalidad máxima). Nótese que ambos, el CIF de la figura 1a y el CIF de la figura 1b son maximales, pero únicamente el CIF de la figura 1b es máximo. Encontrar el CIF máximo es en general un problema NP-difícil, incluso para el caso de que la gráfica de entrada es plana. Se dice que una gráfica es plana, cuando dicha gráfica puede dibujarse en el plano sin que sus aristas se crucen.
El hecho de que un problema pertenezca a la clase de problemas NP-difícil, implica que hasta la fecha no se conocen algoritmos que puedan solucionar este problema, para cualquier instancia del mismo, en tiempo polinomial (es decir, en un tiempo suficientemente factible para llevarlo a su implementación). Por ejemplo, obtener un CIF máximo para una gráfica con algunos cientos de nodos podría tomar varias horas en una computadora tradicional, con algunos miles de nodos, podría tomar varios días. Se sabe, sin embargo, que, para cierto tipo de gráficas planas, por ejemplo, para los árboles y para las gráficas cactus, el problema de encontrar un CIF máximo, admite soluciones en tiempo polinomial.
Investigación Boletín Mensual 11 de Información