NETCOM Research Group

Luis F. Chiroque, Estudiante de doctorado en IMDEA Networks, participó recientemente en un prestigioso taller internacional en Wadern, Alemania, versando sobre el problema del isomorfismo de gráficos*, y los recientes descubrimientos realizados en relación con éste, que se analizaron entre 40 investigados de todo el mundo, especialmente invitados para el evento.

IMDEA Networks participó en el taller del Dr. Laszlo Babai – un Investigador húngaro altamente reconocido y Profesor de Informática y Matemática en la Universidad de Chicago, Estados Unidos. El investigador presentó sus notables resultados de investigación relacionados con el problema del isomorfismo de gráficos (GI por sus siglas en inglés): hace poco, el Dr. Babai propuso un nuevo algoritmo destinado a solucionar el problema, y comparado con algoritmos sugeridos anteriormente, este algoritmo ofrece un nivel de complejidad sólo casi-polinómico. Esto constituye un importante avance teniendo en cuenta que los mejores resultados anteriores eran casi-exponenciales, lo cual significa que al poner a prueba el GI con gráficos grandes, el proceso de análisis podría ser cuestión de horas en lugar de días como ha sido el caso hasta ahora.

Hoy día, el problema del GI es uno de los únicos problemas computacionales naturales en el que sigue sin resolverse la complejidad. Por consiguiente, una explicación aproximada del problema es que se trata básicamente de decidir si dos gráficos determinados son estructuralmente distintos, o si uno es simplemente una versión agitada del otro. Resulta sumamente complicado llegar a un acuerdo, ya que hay varias comunidades con cada una su punto de vista sobre el problema y no menos importante en su solución. Por lo tanto, para mencionar sólo algunos de los grupos opuestos, existen los profesionales, los lógicos, los teóricos de grupos algorítmicos, teóricos de gráficos, teóricos de complejidad, e investigadores y científicos del área de optimización combinatoria. Estas últimas comunidades procuran emplear diferentes técnicas de isomorfismo en sus estudios, con lo cual adoptan un enfoque práctico al problema teórico. Justamente la investigación que se lleva a cabo en IMDEA Networks, por el Estudiante de doctorado, Luis F. Chiroque, entre otros investigadores, se basa en tal enfoque práctico a un problema teórico (véanse las publicaciones presentadas a continuación).

El taller tuvo lugar en Schloss Dagstuhl, en Alemania, reconocida en la comunidad de informáticos como un sitio de renombre para intercambiar ideas y tratar los resultados de sus investigaciones. El evento fue una reunión entre más de 40 investigadores de todo el mundo, todos dedicándose al problema GI. La asistencia a este evento era sólo por invitación. A lo largo de los cinco días del taller se hicieron 20 ponencias, empezando por Dr. Lázsló Babai quien dio dos ponencias al principio del evento. Primero, hizo un boceto de su algoritmo, y después prosiguió a hablar en detalle de los aspectos específicos del problema. Durante el evento, varias diferencias importantes entre los enfoques teóricos y prácticos se manifestaron. Ante todo, quedó claro que los avances teóricos raras veces se reflejan en la práctica. Por consiguiente, cabe destacar que queda mucho por recorrer antes de que se establezca una solución en este campo científico.

El programa del evento dejó espacio para analizar los actuales problemas sin resolver, tales como el isomorfismo de cadenas, Intersección de subconjuntos, así como los sub-problemas relacionados con estas áreas. Además,  los investigadores asistentes fueron invitados en el evento a presentar sus actividades científicas actuales, con el fin de dar paso a un debate y dar la bienvenida a nuevas propuestas. Por último, los organizadores del evento animaron a los participantes a establecer nuevas colaboraciones entre ellos.

* El Problema del Isomorfismo Gráfico es uno de los únicos problemas computacionales naturales que sigue sin resolverse, por consiguiente, una explicación aproximada del problema es que se trata básicamente de decidir si dos gráficos determinados son estructuralmente distintos, o si uno es simplemente una versión agitada del otro.