Vuelven los seminarios de Grafos
¡Rápido, péguenles a esos (grafos) menores!
Expone: Eric Brandwein
Día y lugar: Lunes 20/04 a las 14 hs. en la sala de reuniones 2119 del Pabellón 0+infinito.
Expositor: Eric Brandwein
Resumen: El problema de Vertex Cover consiste en eliminar la mínima cantidad de vértices de un grafo G tal que no quede ninguna arista. "Pegarles" a estas aristas con vértices de G se puede ver como eliminar todas las copias de un grafo H en G, donde H es solo dos vértices conectados por una arista. Esta idea se puede generalizar a cualquier grafo H. Además, podríamos querer pegarle a H no en términos de subgrafos, pero en términos de menores. Un menor de un grafo G es el resultado de eliminar algunos vértices, eliminar algunas aristas, y contraer otras aristas de G. Esta charla se centra en el problema general de F-Deletion, que consiste en encontrar la mínima cantidad de vértices a eliminar para pegarle a todos los menores de una familia F. Como estos problemas son casi todos NP-hard, nos restringimos a resolverlos cuando el grafo de entrada cumple algunas propiedades particulares. Incluso nos preguntamos: ¿qué propiedades particulares tiene que cumplir el grafo para que efectivamente se pueda resolver F-Deletion rápidamente? En específico, y para los entendidos (lo vamos a explicar en la charla, no se preocupen), ¿para qué parametros estructurales de G es que F-Deletion admite un kernel polinomial?
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/+
