Compresión iterativa

En informática , la compresión iterativa es una técnica algorítmica para el diseño de algoritmos tratables con parámetros fijos , en la que se añade un elemento (como un vértice de un grafo ) al problema en cada paso, y se utiliza una pequeña solución para el problema anterior a la adición para ayudar a encontrar una pequeña solución para el problema posterior al paso.

La técnica fue inventada por Reed, Smith y Vetta ^{[ 1 ]} para demostrar que el problema de la transversalidad de ciclos impares era resoluble en tiempo O (3 ^k kmn )  , para un grafo con n vértices, m aristas y un número k de transversalidad de ciclos impares . La transversalidad de ciclos impares es el problema de encontrar el conjunto más pequeño de vértices de un grafo que incluya al menos un vértice de cada ciclo impar; su complejidad parametrizada fue una cuestión abierta durante mucho tiempo. ^{[ 2 ] [ 3 ]} Esta técnica demostró posteriormente ser muy útil para mostrar resultados de tratabilidad con parámetros fijos . Ahora se considera una de las técnicas fundamentales en el área de la algoritmia parametrizada.

La compresión iterativa se ha utilizado con éxito en muchos problemas, por ejemplo, la transversalidad de ciclos impares (véase más abajo) y la bipartición de aristas , el conjunto de vértices de retroalimentación y la eliminación de vértices de clúster. ^{[ 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 grafos parametrizados cuyas entradas son un grafo G = ( V , E ) y un número natural k , y donde el problema consiste en probar la existencia de una solución (un conjunto de vértices) de tamaño ≤ k . Supongamos que el problema tiene las siguientes propiedades:

• Es cerrado bajo subgrafos inducidos : si existe una solución de tamaño ≤ k en un grafo dado, entonces también existe una solución de este tamaño o menor en cada subgrafo inducido.
• Si X es una solución y X' es un conjunto de vértices que contienen a X , entonces X' también es una solución.
• Existe una subrutina eficiente que, dada una solución Y de tamaño k  +  1 , determina si puede comprimirse a una solución de tamaño k . Es decir, encuentra una solución de tamaño k o determina que no existe tal solución.

Si se cumplen estos supuestos, entonces el problema se puede resolver agregando vértices uno por uno a un subgrafo inducido y encontrando la solución para el subgrafo inducido, de la siguiente manera:

1. Partimos de un subgrafo inducido por un conjunto de vértices S de tamaño k , y una solución X que es igual a S mismo. (Si X no es una solución de S, entonces no existe ninguna solución).
2. Mientras S ≠ V , realice los siguientes pasos:
   • Sea v cualquier vértice de V \ S , y agregue v a S
   • Comprueba si la solución de ( k + 1) vértices Y = X ∪ {v } a S se puede comprimir a una solución de k vértices.
   • Si no se puede comprimir, aborte el algoritmo: el grafo de entrada no tiene solución de k vértices.
   • De lo contrario, establezca X en la nueva solución comprimida y continúe el bucle.

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 con parámetros fijos, es decir, f ( k )  · n ^c para alguna constante c , entonces el procedimiento de compresión iterativo que resuelve todo el problema se ejecuta en un tiempo de f ( k ) · n ^{c +1} . La misma técnica se puede aplicar para encontrar conjuntos de aristas para propiedades de grafos cerradas 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 exponencial o 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.   

Una transversal de ciclo impar de un grafo es un conjunto de vértices que se pueden eliminar para hacer que el grafo sea bipartito. En su artículo original, Reed et al. dieron un algoritmo de compresión iterativa para determinar si un grafo tiene una transversal de ciclo impar de tamaño como máximo k , en tiempo O (3 ^k kmn ). Posteriormente, Lokshstanov, Saurabh y Sikdar dieron un algoritmo más simple, también usando compresión iterativa. ^{[ 6 ]} Para comprimir un conjunto de eliminación Y de tamaño k + 1 a un conjunto de eliminación X de tamaño k , su algoritmo prueba todas las 3 ^{k + 1} particiones de Y en tres subconjuntos: el subconjunto de Y que pertenece al nuevo conjunto de eliminación y los dos subconjuntos de Y que pertenecen a los dos lados del grafo bipartito que queda después de eliminar X . Una vez que se han seleccionado estos tres conjuntos, los vértices restantes de un conjunto de eliminación X (si existe) se pueden encontrar a partir de ellos aplicando un algoritmo de corte mínimo de flujo máximo . 

El problema de la cobertura de vértices es otro ejemplo en el que se puede emplear la compresión iterativa. En este problema, se introduce un grafo G  =  ( V , E ) y un número natural k , y el algoritmo debe determinar si existe un conjunto X de k vértices tal que cada arista sea incidente a un vértice en X. En la variante de compresión del problema, la entrada es un conjunto Y de k  +  1 vértices incidentes a todas las aristas del grafo, y el algoritmo debe encontrar un conjunto X de tamaño k con la misma propiedad, si existe. Una forma de hacerlo es probar las 2k ^{+ 1 opciones posibles para determinar} qué subconjunto de Y se debe eliminar de la cobertura y reintroducir en el grafo. Dicha elección solo funcionará si no hay dos vértices eliminados adyacentes, y para cada elección, la subrutina debe incluir en la cobertura todos los vértices fuera de Y que sean incidentes a una arista que quede descubierta tras esta eliminación. El uso de esta subrutina en un algoritmo de compresión iterativo proporciona un algoritmo simple O (2 ^k n ² )  para la cobertura de vértices.

• Kernelización , una técnica de diseño diferente para algoritmos tratables con parámetros fijos.