Complejidad parametrizada

Ponente(s): José Alberto Fernández Zepeda

En esta plática se ilustran dos técnicas básicas utilizadas en el área de complejidad parametrizada: La kernelización y la ramificación acotada. Estas técnicas se ejemplifican al resolver un caso especial del problema de cubrimientos de vértices, en su versión de decisión, el cual es un problema NP-completo. Un algoritmo de kernelización toma como entrada un caso específico de algún problema computacional y por medio de una serie de reglas resuelve la parte “fácil” del problema. La salida de este algoritmo es un problema más pequeño, llamado kernel o núcleo, el cual se caracteriza por ser la parte más difícil de resolver del problema original. Lo ramificación acotada es una técnica que emplea árboles de una altura acotada para evaluar todas las posibles soluciones a un problema dado, en nuestro ejemplo lo usamos para resolver el kernel.