En ciencias de la computación , la compresión iterativa es una técnica algorítmica para el diseño de algoritmos manejables de parámetros fijos , en la que un elemento (como un vértice de un gráfico ) se agrega al problema en cada paso, y una pequeña solución para el problema antes a la suma se utiliza para ayudar a encontrar una pequeña solución al problema después del paso.
La técnica fue inventada por Reed, Smith y Vetta [1] para mostrar que el problema de ciclo impar transversal se podía resolver en el tiempo O (3 k kmn ) , para una gráfica con n vértices, m aristas y número impar de ciclo transversal k . El ciclo impar transversal es el problema de encontrar el conjunto más pequeño de vértices de una gráfica que incluya al menos un vértice de cada ciclo impar; su complejidad parametrizada era una cuestión abierta desde hace mucho tiempo. [2] [3] Posteriormente, esta técnica demostró ser muy útil para mostrar la manejabilidad de parámetros fijosresultados. Ahora se considera una de las técnicas fundamentales en el área de la algorítmica parametrizada.
La compresión iterativa se ha utilizado con éxito en muchos problemas, por ejemplo, ciclo impar transversal (ver más abajo) y bipartización de bordes , conjunto de vértices de retroalimentación , eliminación de vértices de clúster y conjunto de vértices de retroalimentación dirigida. [4] También se ha utilizado con éxito para algoritmos de tiempo exponencial exacto para conjuntos independientes . [5]
La compresión iterativa se aplica, por ejemplo, a problemas de gráficos parametrizados cuyas entradas son un gráfico G = ( V , E ) y un número natural k , y donde el problema es probar la existencia de una solución (un conjunto de vértices) de tamaño ≤ k . Suponga que el problema se cierra bajo subgrafos inducidos (si existe una solución de tamaño ≤ k en un gráfico dado, entonces también existe una solución de este tamaño o menor en cada subgrafo inducido) y que existe una subrutina eficiente que determina si una solución Y de tamaño k + 1se puede comprimir a una solución más pequeña de tamaño k .
Si se cumplen estos supuestos, entonces el problema se puede resolver agregando vértices uno a la vez a un subgrafo inducido y encontrando la solución al subgrafo inducido, de la siguiente manera:
Este algoritmo llama a la subrutina de compresión un número lineal de veces. Por lo tanto, si la variante de compresión se puede resolver en un tiempo manejable de parámetro fijo, es decir, f ( k ) · n c para alguna constante c , entonces el procedimiento de compresión iterativa que resuelve todo el problema se ejecuta en f ( k ) · n c +1 tiempo . La misma técnica se puede aplicar para encontrar conjuntos de aristas para propiedades de gráficos cerrados bajo subgrafos (en lugar de subgrafos inducidos), o para otras propiedades más allá de la teoría de grafos. Cuando se desconoce el valor del parámetro k , se puede encontrar utilizando un nivel externo de búsqueda exponencialo búsqueda secuencial para la elección óptima de k , con cada paso de la búsqueda basado en el mismo algoritmo de compresión iterativo.