Los invitamos a un nuevo encuentro del seminario de grafos, el próximo lunes 01/06 a las 14 hs. en la sala de reuniones 2119 del Pabellón 0+infinito. 

Expositor: Ignacio Maqueda

Título: One Gate to Rule Them All Out: Propagación en clases hereditarias de grafos

Resumen:

Muchas clases de grafos se describen prohibiendo ciertos subgrafos inducidos. Sin embargo, contar con una caracterización estructural no siempre implica tener un algoritmo eficiente para reconocer cuándo un grafo pertenece a la clase. 

En esta charla presentamos un enfoque general para abordar este problema usando sistemas lineales asociados al conteo de subgrafos inducidos. La idea central es elegir un subgrafo distinguido, al que llamamos gate, cuya ausencia pueda verificarse eficientemente. Luego, podemos usar esa información para propagar restricciones que certifiquen la ausencia de otras configuraciones prohibidas. 

Veremos que este enfoque da lugar a distintos comportamientos algorítmicos: en algunos casos alcanza para reconocer completamente la clase, mientras que en otras reduce el problema a detectar una única obstrucción residual o incluso a resolver un problema estructural más simple, como testear si un grafo es o no bipartito.

Son todos bienvenidos y si están interesados en participar frecuentemente en este seminario, los invitamos a unirse a nuestro grupo de Telegram: https://t.me/+RkVxwjjIdiE1Yjkx y visitar la página del seminario: https://web.dm.uba.ar/index.php/investigacion/seminarios/seminario-grafos .