Plegabilidad: un nuevo parámetro de ancho

Resumen:

Muchos de los problemas en grafos que buscamos resolver son NP-completos en general. Sin embargo, esto no significa que debamos rendirnos. Al restringir la clase de grafos, es posible aprovechar su estructura para diseñar algoritmos eficientes. Una forma clásica de lograrlo es mediante parámetros de ancho, que miden cuán lejos está un grafo de tener una estructura simple.  
En esta charla presentamos un nuevo parámetro de ancho, que llamamos provisoriamente plegabilidad. Un grafo es k-plegable si existe un orden de sus vértices y una partición de los mismos en k clases tal que, para toda arista vw con v < w, ningún vértice u ubicado entre v y w pertenece a la misma clase que v ni a la misma clase que w. Los grafos 1-plegables son exactamente los bosques lineales, por lo que la plegabilidad puede pensarse como una medida de la distancia a esta clase. 
Estudiamos la complejidad de problemas relacionados con la plegabilidad, la relacionamos con otros parámetros conocidos. Luego caracterizamos la estructura de los grafos 2-plegables, los cuales tienen una estructura muy particular. Finalmente, discutimos el comportamiento de la plegabilidad frente a subdivisiones y supresiones de vértices, y las preguntas abiertas para plegabilidades mayores.