- ¿Cómo explicarías el tema de tu tesis doctoral?
Todos conocemos los grafos y que hay problemas computacionales sobre grafos que tardan mucho tiempo en ser resueltos. Ahora, algunos de estos problemas son difíciles cuando estás considerando resolverlos para un grafo del que no sabés nada pero a veces, dependiendo de la información extra que tengas del grafo, podés hacer algún preprocesamiento rápido del grafo que te facilite las cosas, sacando quizá vértices o aristas que no afectan a tu problema. Luego, teniendo este nuevo grafo más chiquito, ahí sí corrés algún algoritmo que tarde mucho tiempo (en términos del tamaño del grafo chiquito), y tenés la respuesta para el grafo original. O sea que para saber la respuesta a tu problema, en vez de correr el algoritmo lento en tu grafo original, primero achicás el grafo, y después corrés el algoritmo lento, ahorrando tiempo.
La información extra que podés tener de un grafo se llama «parámetro» de un grafo, y es un numerito que depende del grafo. Lo que yo hago es investigar para qué problemas de grafos y para qué parámetros de grafos existe este preprocesamiento que mencioné, y cuánto podría achicar el grafo con este preprocesamiento.
- ¿Qué ejemplos de aplicaciones existen de este tema?
Casi siempre que tengas un problema interesante sobre grafos en la vida real, vas a tener que resolver un problema difícil (NP-hard para los entendidos). Pero también lo más probable es que los grafos que estás considerando tengan algún parámetro acotado, o sea, chiquito. Podés entonces aplicar un preprocesamiento, tal cual mencioné antes, para achicar tu grafo de entrada, y efectivamente resolver tu problema de la vida real.
Para una aplicación particular, uno de los problemas que yo investigo es una generalización de vertex cover, que es el problema de encontrar un mínimo conjunto de vértices que, al sacarlos del grafo, te quede el grafo sin aristas. Este problema aparece en muchos lados, como por ejemplo en seguridad de redes, posicionamiento de sensores, monitoreo de infraestructura, y biología computacional.
- ¿Cómo te gustaría continuar luego de tu doctorado?
Ya tuve una propuesta, que no está 100% confirmada, de hacer un postdoc en Francia en temas de grafos el año que viene, así que en principio son dos años que voy a estar con eso. Después probablemente continúe por el lado académico, con un cargo fijo en algún lugar de Europa, si lo consigo. La verdad que me enamoré de la investigación y ¡no creo que la vaya a dejar ir dentro de poco!
- Te propongo un “ping pong” de gustos e intereses…
¿Una película? Primer
¿Una serie? Pantheon
¿Una banda y un disco? Thank you Scientist – Stranger Heads Prevail
¿Un libro? Harry Potter and the Methods of Rationality
¿Una frase o cita favorita? Una que encontré recién: «When a flower doesn’t bloom, you fix the environment in which it grows, not the flower.» – Alexander den Heijer
—————————–
Nombre y apellido: Eric Brandwein.
Inicio de doctorado: Mayo de 2023.
Directores: Flavia Bonomo e Ignasi Sau.
Grupo de Investigación: Grupo de Grafos y Optimización.
Sitio Web: https://www-2.dc.uba.ar/grupinv/grafos/
