Reconocimiento de grafos cuasi-cluster y multipartitos acotados

Día y lugar: Lunes 13/04 a las 14 hs en la sala de reuniones 2119 del Pabellón 0+infinito. 

Expositor: Min Chih Lin (Oscar)

Título: Reconocimiento de grafos cuasi-cluster y multipartitos acotados

Resumen:

Estudiamos las clases de grafos  y , que modelan grafos globalmente cercanos a ser, respectivamente, completamente -multipartitos o agrupables en  cliques, permitiendo al mismo tiempo una cantidad acotada de desviación local por vértice. Estas clases refinan los problemas clásicos de coloreo y clustering mediante la introducción de un parámetro  que controla la cantidad de inconsistencias locales que puede presentar cada vértice. 

Para valores fijos de  y , se sabe que la clase admite caracterizaciones mediante una familia finita de subgrafos inducidos prohibidos. Sin embargo, salvo para algunos pocos valores pequeños de los parámetros, dichas caracterizaciones son puramente existenciales y no conducen a algoritmos implementables de reconocimiento. Cerramos esta brecha mostrando que los grafos suficientemente grandes de  exhiben un fenómeno estructural nítido: por encima de un umbral natural de tamaño, una clase de color completa se vuelve identificable algorítmicamente utilizando únicamente información local de grados. 

Esta observación da lugar a un algoritmo de reconocimiento simple y completamente  constructivo que extrae iterativamente clases de color forzadas y reduce el problema a instancias residuales de tamaño acotado. El algoritmo resultante corre en tiempo ,  donde  depende únicamente de los parámetros fijos. 

Mostramos además que el mismo principio de extracción se aplica, bajo complementación, a la clase  de grafos cuasi-cluster, obteniendo así algoritmos de reconocimiento eficientes y constructivos también en ese contexto. 

Nuestros resultados muestran cómo propiedades estructurales puramente existenciales pueden transformarse en algoritmos explícitos y eficientes, y destacan el papel de las cotas sobre desviaciones locales como mecanismo para recuperar tractabilidad en problemas de descomposición que, en general, son difíciles.