Kernelización

En informática , una kernelización es una técnica para diseñar algoritmos eficientes que alcanzan su eficiencia mediante una etapa de preprocesamiento en la que las entradas al algoritmo se reemplazan por una entrada más pequeña, llamada "núcleo". El resultado de resolver el problema en el kernel debería ser el mismo que en la entrada original, o debería ser fácil transformar la salida en el kernel a la salida deseada para el problema original.

La kernelización a menudo se logra aplicando un conjunto de reglas de reducción que eliminan partes de la instancia que son fáciles de manejar. En la teoría de la complejidad parametrizada , a menudo es posible demostrar que un núcleo con límites garantizados en el tamaño de un núcleo (en función de algún parámetro asociado al problema) se puede encontrar en tiempo polinomial . Cuando esto es posible, da como resultado un algoritmo manejable de parámetros fijos cuyo tiempo de ejecución es la suma del paso de kernelización (tiempo polinómico) y el tiempo (no polinómico pero limitado por el parámetro) para resolver el kernel. De hecho, todo problema que pueda resolverse mediante un algoritmo manejable de parámetros fijos puede resolverse mediante un algoritmo de kernelización de este tipo. Esto también es válido para la kernelización aproximada .

Ejemplo: cobertura de vértice

Un ejemplo estándar de algoritmo de kernelización es la kernelización del problema de cobertura de vértices de S. Buss. ^[1] En este problema, la entrada es un gráfico no dirigido junto con un número . La salida es un conjunto de, como máximo, vértices que incluye un punto final de cada borde del gráfico, si dicho conjunto existe, o una excepción de error si no existe dicho conjunto. Este problema es NP-difícil . Sin embargo, se pueden utilizar las siguientes reglas de reducción para kernelizarlo: ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle k}$

1. Si y es un vértice de grado mayor que , elimínelo de la gráfica y disminuya en uno. Cada cubierta de vértice de tamaño debe contener, ya que de lo contrario habría que seleccionar demasiados de sus vecinos para cubrir los bordes incidentes. Por lo tanto, se puede formar una cobertura de vértice óptima para el gráfico original a partir de una cobertura del problema reducido agregando nuevamente a la cobertura. ${\displaystyle k>0}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle v}$
2. Si es un vértice aislado, elimínelo. Un vértice aislado no puede cubrir ninguna arista, por lo que en este caso no puede formar parte de ninguna cobertura mínima. ${\displaystyle v}$ ${\displaystyle v}$
3. Si quedan más de aristas en el gráfico y no se puede aplicar ninguna de las dos reglas anteriores, entonces el gráfico no puede contener una cobertura de vértices de tamaño . Porque, después de eliminar todos los vértices de grado mayor que , cada vértice restante solo puede cubrir la mayoría de los bordes y un conjunto de vértices solo puede cubrir la mayoría de los bordes. En este caso, la instancia puede ser reemplazada por una instancia con dos vértices, una arista y , que tampoco tiene solución. ${\displaystyle k^{2}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k^{2}}$ ${\displaystyle k=0}$

Un algoritmo que aplica estas reglas repetidamente hasta que no se puedan hacer más reducciones necesariamente termina con un núcleo que tiene como máximo aristas y (porque cada arista tiene como máximo dos puntos finales y no hay vértices aislados) con la mayoría de vértices. Esta kernelización puede implementarse en tiempo lineal . Una vez que se ha construido el núcleo, el problema de la cobertura de vértices se puede resolver mediante un algoritmo de búsqueda de fuerza bruta que prueba si cada subconjunto del núcleo es una cubierta del núcleo. Por lo tanto, el problema de cobertura de vértices se puede resolver a tiempo para un gráfico con vértices y aristas, lo que permite resolverlo de manera eficiente cuando es pequeño incluso si y son grandes. ${\displaystyle k^{2}}$ ${\displaystyle 2k^{2}}$ ${\displaystyle O(2^{2k^{2}}+n+m)}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle m}$

Aunque este límite es manejable con parámetros fijos, su dependencia del parámetro es mayor de lo que podría desearse. Los procedimientos de kernelización más complejos pueden mejorar este límite al encontrar kernels más pequeños, a expensas de un mayor tiempo de ejecución en el paso de kernelización. En el ejemplo de cobertura de vértices, se conocen algoritmos de kernelización que producen núcleos con como máximo vértices. Un algoritmo que logra este límite mejorado explota la semiintegralidad de la relajación del programa lineal de la cobertura de vértices debido a Nemhauser y Trotter. ^[2] Otro algoritmo de kernelización que logra ese límite se basa en lo que se conoce como regla de reducción de corona y utiliza argumentos de ruta alterna . ^[3] El algoritmo de kernelización más conocido actualmente en cuanto al número de vértices se debe a Lampis (2011) y logra vértices para cualquier constante fija . ${\displaystyle 2k}$ ${\displaystyle 2k-c\log k}$ ${\displaystyle c}$

En este problema no es posible encontrar un núcleo de tamaño , a menos que P = NP, ya que dicho núcleo conduciría a un algoritmo de tiempo polinómico para el problema de cobertura de vértice duro NP. Sin embargo, en este caso se pueden demostrar límites mucho más fuertes en el tamaño del núcleo: a menos que coNP NP/poly (lo que los teóricos de la complejidad creen improbable ), para cada es imposible en tiempo polinomial encontrar núcleos con aristas. ^[4] Se desconoce para la cobertura de vértices si los núcleos con vértices para algunos tendrían consecuencias poco probables en la teoría de la complejidad. ${\displaystyle O(\log k)}$ ${\displaystyle \subseteq }$ ${\displaystyle \epsilon >0}$ ${\displaystyle O(k^{2-\epsilon })}$ ${\displaystyle (2-\epsilon )k}$ ${\displaystyle \epsilon >0}$

Definición

En la literatura, no existe un consenso claro sobre cómo se debe definir formalmente la kernelización y existen diferencias sutiles en los usos de esa expresión.

Notación de Downey-Fellows

En la notación de Downey y Fellows (1999), un problema parametrizado es un subconjunto que describe un problema de decisión . ${\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }$

Una kernelización para un problema parametrizado es un algoritmo que toma una instancia y la asigna en un polinomio de tiempo en y hacia una instancia tal que ${\displaystyle L}$ ${\displaystyle (x,k)}$ ${\displaystyle |x|}$ ${\displaystyle k}$ ${\displaystyle (x',k')}$

• ${\displaystyle (x,k)}$está en si y sólo si está en , ${\displaystyle L}$ ${\displaystyle (x',k')}$ ${\displaystyle L}$
• el tamaño de está limitado por una función computable en , y ${\displaystyle x'}$ ${\displaystyle f}$ ${\displaystyle k}$
• ${\displaystyle k'}$está acotado por una función en . ${\displaystyle k}$

El resultado de la kernelización se llama kernel. En este contexto general, el tamaño de la cuerda simplemente se refiere a su longitud. Algunos autores prefieren utilizar el número de vértices o el número de aristas como medida de tamaño en el contexto de problemas de gráficos. ${\displaystyle (x',k')}$ ${\displaystyle x'}$

Notación Flum-Grohe

En la notación de Flum & Grohe (2006, p. 4), un problema parametrizado consta de un problema de decisión y una función , la parametrización. El parámetro de una instancia es el número . ${\displaystyle L\subseteq \Sigma ^{*}}$ ${\displaystyle \kappa :\Sigma ^{*}\to \mathbb {N} }$ ${\displaystyle x}$ ${\displaystyle \kappa (x)}$

Una kernelización para un problema parametrizado es un algoritmo que toma una instancia con parámetro y la asigna en tiempo polinomial a una instancia tal que ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle y}$

• ${\displaystyle x}$está en si y sólo si está en y ${\displaystyle L}$ ${\displaystyle y}$ ${\displaystyle L}$
• el tamaño de está limitado por una función computable en . ${\displaystyle y}$ ${\displaystyle f}$ ${\displaystyle k}$

Tenga en cuenta que en esta notación, el límite del tamaño de implica que el parámetro de también está limitado por una función en . ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle k}$

La función a menudo se denomina tamaño del núcleo. Si , se dice que admite un núcleo polinomial. De manera similar, para , el problema admite núcleo lineal. ${\displaystyle f}$ ${\displaystyle f=k^{O(1)}}$ ${\displaystyle L}$ ${\displaystyle f={O(k)}}$

La kernelizabilidad y la trazabilidad de parámetros fijos son equivalentes

Un problema es manejable con parámetros fijos si y sólo si es kernelizable y decidible .

Que un problema kernelizable y decidible es manejable con parámetros fijos se puede ver en la definición anterior: primero, se invoca el algoritmo de kernelización, que se ejecuta en el tiempo para algunos c, para generar un kernel de tamaño . Luego, el núcleo se resuelve mediante el algoritmo que demuestra que el problema es decidible. El tiempo total de ejecución de este procedimiento es , donde es el tiempo de ejecución del algoritmo utilizado para resolver los núcleos. Dado que es computable, por ejemplo, utilizando el supuesto de que es computable y probando todas las entradas posibles de longitud , esto implica que el problema es manejable con parámetros fijos. ${\displaystyle O(|x|^{c})}$ ${\displaystyle f(k)}$ ${\displaystyle g(f(k))+O(|x|^{c})}$ ${\displaystyle g(n)}$ ${\displaystyle g(f(k))}$ ${\displaystyle f(k)}$ ${\displaystyle f(k)}$

La otra dirección, que un problema manejable con parámetros fijos es kernelizable y decidible, es un poco más complicada. Supongamos que la pregunta no es trivial, lo que significa que hay al menos una instancia que está en el idioma, llamada , y al menos una instancia que no está en el idioma, llamada ; de lo contrario, reemplazar cualquier instancia por la cadena vacía es una kernelización válida. Supongamos también que el problema es manejable con parámetros fijos, es decir, tiene un algoritmo que se ejecuta en la mayoría de los pasos de las instancias , para alguna constante y alguna función . Para kernelizar una entrada, ejecute este algoritmo en la entrada dada durante la mayoría de los pasos. Si termina con una respuesta, use esa respuesta para seleccionar o como núcleo. Si, en cambio, excede el límite de número de pasos sin terminar, entonces regresa como núcleo. Debido a que sólo se devuelve como núcleo para entradas con , se deduce que el tamaño del núcleo producido de esta manera es como máximo . Este límite de tamaño es computable, según el supuesto de que la manejabilidad de parámetros fijos es computable. ${\displaystyle I_{yes}}$ ${\displaystyle I_{no}}$ ${\displaystyle f(k)\cdot |x|^{c}}$ ${\displaystyle (x,k)}$ ${\displaystyle c}$ ${\displaystyle f(k)}$ ${\displaystyle |x|^{c+1}}$ ${\displaystyle I_{yes}}$ ${\displaystyle I_{no}}$ ${\displaystyle |x|^{c+1}}$ ${\displaystyle (x,k)}$ ${\displaystyle (x,k)}$ ${\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1}}$ ${\displaystyle \max\{|I_{yes}|,|I_{no}|,f(k)\}}$ ${\displaystyle f(k)}$

Más ejemplos

• Cobertura de vértice parametrizada por el tamaño de la cobertura de vértice: el problema de cobertura de vértice tiene núcleos con como máximo vértices y aristas. ^[5] Además, para cualquier , la cobertura de vértices no tiene núcleos con aristas a menos que . ^[4] Los problemas de cobertura de vértices en hipergrafías uniformes tienen núcleos con bordes que utilizan el lema del girasol y no tienen núcleos de tamaño a menos que . ^[4] ${\displaystyle 2k}$ ${\displaystyle O(k^{2})}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle O(k^{2-\varepsilon })}$ ${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$ ${\displaystyle d}$ ${\displaystyle O(k^{d})}$ ${\displaystyle O(k^{d-\varepsilon })}$ ${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$
• Conjunto de vértices de retroalimentación parametrizado por el tamaño del conjunto de vértices de retroalimentación: El problema del conjunto de vértices de retroalimentación tiene núcleos con vértices y aristas. ^[6] Además, no tiene granos con bordes a menos que . ^[4] ${\displaystyle 4k^{2}}$ ${\displaystyle O(k^{2})}$ ${\displaystyle O(k^{2-\varepsilon })}$ ${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$
• ${\displaystyle k}$-path: El problema de -path es decidir si un gráfico dado tiene una ruta de al menos . Este problema tiene núcleos de tamaño exponencial en , y no tiene núcleos de tamaño polinómico en a menos que . ^[7] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$
• Problemas bidimensionales: muchas versiones parametrizadas de problemas bidimensionales tienen núcleos lineales en gráficos planos y, de manera más general, en gráficos que excluyen algunos gráficos fijos como menores . ^[8]

Kernelización para parametrizaciones estructurales.

Si bien el parámetro en los ejemplos anteriores se elige como el tamaño de la solución deseada, esto no es necesario. También es posible elegir como valor del parámetro una medida de complejidad estructural de la entrada, lo que da lugar a las llamadas parametrizaciones estructurales. Este enfoque es fructífero para casos cuyo tamaño de solución es grande, pero para los cuales alguna otra medida de complejidad está limitada. Por ejemplo, el número de vértices de retroalimentación de un gráfico no dirigido se define como la cardinalidad mínima de un conjunto de vértices cuya eliminación lo vuelve acíclico. El problema de cobertura de vértices parametrizado por el número de vértice de retroalimentación del gráfico de entrada tiene una kernelización polinomial: ^[9] Existe un algoritmo de tiempo polinomial que, dado un gráfico cuyo número de vértice de retroalimentación es , genera un gráfico en vértices tal que un vértice mínimo cover in se puede transformar en una cobertura de vértice mínima en tiempo polinómico. Por lo tanto, el algoritmo de kernelización garantiza que las instancias con un número de vértices de retroalimentación pequeño se reduzcan a instancias pequeñas. ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G'}$ ${\displaystyle O(k^{3})}$ ${\displaystyle G'}$ ${\displaystyle G}$ ${\displaystyle k}$

Ver también

• Compresión iterativa , una técnica de diseño diferente para algoritmos manejables de parámetros fijos
• Kernelización aproximada , para problemas de optimización un kernel puede perder un factor determinado en la calidad de la solución

Notas

1. Esta observación inédita se reconoce en un artículo de Buss & Goldsmith (1993)
2. Flum y Grohe (2006)
3. Flum y Grohe (2006) dan un núcleo basado en la reducción de la corona que tiene vértices. El vértice encuadernado es un poco más complicado y folclórico. ${\displaystyle 3k}$ ${\displaystyle 2k}$
4. Dell y van Melkebeek (2010)
5. Chen, Kanj y Jia (2001)
6. Thomassé (2010)
7. Bodlaender y col. (2009)
8. Fomín y col. (2010)
9. Jansen y Bodlaender (2013)

Referencias

• Abu-Khzam, Faisal N.; Collins, Rebecca L.; Becarios, Michael R .; Langston, Michael A .; Suters, W. Henry; Symons, Chris T. (2004), Algoritmos de kernelización para el problema de la cobertura de vértices: teoría y experimentos (PDF) , Universidad de Tennessee.
• Bodlaender, Hans L .; Downey, Rod G .; Becarios, Michael R .; Hermelin, Danny (2009), "Sobre problemas sin núcleos polinomiales", Journal of Computer and System Sciences , 75 (8): 423–434, doi : 10.1016/j.jcss.2009.04.001.
• Buss, Jonathan F.; Goldsmith, Judy (1993), "No determinismo interno ", SIAM Journal on Computing , 22 (3): 560–572, doi :10.1137/0222038, S2CID  43081484 ${\displaystyle P^{*}}$.
• Chen, Jianer; Kanj, Iyad A.; Jia, Weijia (2001), "Cobertura de Vertex: más observaciones y mejoras", Journal of Algorithms , 41 (2): 280–301, doi :10.1006/jagm.2001.1186, S2CID  13557005.
• Dell, Holger; van Melkebeek, Dieter (2010), "La satisfacción no permite una dispersión no trivial a menos que colapse la jerarquía de tiempo polinomial" (PDF) , Actas del 42º Simposio ACM sobre Teoría de la Computación (STOC 2010) (PDF) , págs. doi :10.1145/1806689.1806725, S2CID  1117711.
• Downey, RG ; Fellows, MR (1999), Complejidad parametrizada , monografías en informática, Springer, doi :10.1007/978-1-4612-0515-9, ISBN 0-387-94883-X, SEÑOR  1656112, S2CID  15271852.
• Flum, Jörg; Grohe, Martin (2006), Teoría de la complejidad parametrizada, Springer, ISBN 978-3-540-29952-3, consultado el 5 de marzo de 2010.
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionalidad y núcleos", Actas del 21º Simposio ACM-SIAM sobre algoritmos discretos (SODA 2010) , págs..
• Jansen, diputado Bart; Bodlaender, Hans L. (2013), "Revisión de la kernelización de la cubierta de vértices: límites superior e inferior para un parámetro refinado", Theory Comput. Sistema. , 53 (2): 263–299, arXiv : 1012.4701 , doi : 10.1007/s00224-012-9393-4,
• Lampis, Michael (2011), "Un núcleo de orden 2 k  −  c  log  k para la cobertura de vértices", Information Processing Letters , 111 (23–24): 1089–1091, doi :10.1016/j.ipl.2011.09.003.
• Thomassé, Stéphan (2010), "Un núcleo de 4 k ² para conjunto de vértices de retroalimentación", Transacciones ACM sobre algoritmos , 6 (2): 1–8, doi :10.1145/1721837.1721848, S2CID  7510317.
• Niedermeier, Rolf (2006), Invitación a algoritmos de parámetros fijos, Oxford University Press, CiteSeerX  10.1.1.2.9618 , ISBN 0-19-856607-7, archivado desde el original el 24 de septiembre de 2008 , consultado el 1 de junio de 2017.

Otras lecturas

• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019), Kernelización: teoría del preprocesamiento parametrizado , Cambridge University Press, pág. 528, doi :10.1017/9781107415157, ISBN 978-1107057760
• Niedermeier, Rolf (2006), Invitación a algoritmos de parámetros fijos, Oxford University Press, Capítulo 7, ISBN 0-19-856607-7, archivado desde el original el 29 de septiembre de 2007 , consultado el 1 de junio de 2017
• Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Algoritmos parametrizados , Springer, Capítulos 2 y 9, ISBN 978-3-319-21274-6