Parameterized Algorithms

Tratado exhaustivo y de referencia internacional sobre la algoritmia parametrizada y la teoría de tractabilidad con parámetro fijo (Fixed-Parameter Tractability o FPT), orientado a resolver de manera exacta problemas computacionales NP-difíciles donde los algoritmos en tiempo polinomial clásico no son viables. Al tratarse de un texto de fundamentación matemática y complejidad computacional, es independiente de lenguajes de software específicos. Está concebido para investigadores, profesores y estudiantes de posgrado o cursos avanzados de informática teórica que cuenten con una sólida formación previa en matemáticas discretas, teoría de grafos y teoría de la complejidad computacional clásica (clases P, NP y reducciones polinomiales).

La obra enseña con extremo rigor las técnicas centrales y avanzadas de la disciplina. En su primera parte cubre paradigmas esenciales como la reducción de datos y kernelización (kernelization), árboles de búsqueda acotada (bounded search trees), compresión iterativa (iterative compression), métodos aleatorizados como el color coding y programación dinámica sobre descomposiciones de árboles (tree decompositions y treewidth). En su segunda parte profundiza en herramientas de vanguardia, tales como la técnica Cut & Count, separadores importantes (important separators), ramificación basada en programación lineal, familias representativas en matroides algebraicos y resultados de cota inferior apoyados en reducciones de dureza W[1]/W[2] y la hipótesis del tiempo exponencial (ETH y SETH).

El libro no plantea el desarrollo de proyectos de software ni la codificación en un lenguaje de programación concreto, sino la resolución y demostración formal de problemas algorítmicos al final de cada capítulo, clasificados por dificultad e incluyendo pistas para problemas selectos. Su valor diferencial reside en constituir la obra canónica moderna más completa sobre complejidad parametrizada, unificando décadas de investigación dispersa en artículos académicos. Deja fuera cualquier aspecto de desarrollo de aplicaciones, librerías de software o benchmarks prácticos en máquinas reales. Es un texto indispensable para el ámbito académico que exige un dominio previo riguroso de álgebra lineal, combinatoria y análisis asintótico formal.