Kernelización

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

La kernelización se logra a menudo 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 se puede encontrar un núcleo con límites garantizados en el tamaño de un núcleo (como una función de algún parámetro asociado al problema) en tiempo polinomial . Cuando esto es posible, resulta en un algoritmo manejable de parámetros fijos cuyo tiempo de ejecución es la suma del paso de kernelización (tiempo polinomial) y el tiempo (no polinomial pero acotado por el parámetro) para resolver el núcleo. De hecho, cada problema que se puede resolver con un algoritmo manejable de parámetros fijos se puede resolver con un algoritmo de kernelización de este tipo. Esto también es cierto para la kernelización aproximada .

Ejemplo: cobertura de vértice

Un ejemplo estándar de un 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 vértices como máximo que incluye un punto final de cada arista del gráfico, si existe dicho conjunto, o una excepción de falla si no existe dicho conjunto. Este problema es NP-hard . Sin embargo, se pueden usar 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 , retírelo del gráfico y disminuya en uno. Cada cobertura de vértice de tamaño debe contener ya que de lo contrario se tendrían que elegir demasiados de sus vecinos para cubrir las aristas 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 ser parte de ninguna cobertura mínima. ${\displaystyle v}$ ${\displaystyle v}$
3. Si quedan más de aristas en el grafo y no se puede aplicar ninguna de las dos reglas anteriores, entonces el grafo 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 como máximo aristas y un conjunto de vértices solo podría cubrir como máximo aristas. En este caso, la instancia puede reemplazarse 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) como máximo vértices. Esta kernelización se puede implementar en tiempo lineal . Una vez que se ha construido el núcleo, el problema de 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 cobertura del núcleo. Por lo tanto, el problema de cobertura de vértices se puede resolver a tiempo para un grafo con vértices y aristas, lo que permite resolverlo de manera eficiente cuando es pequeño incluso si y son ambos 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 núcleos 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 la regla de reducción de corona y utiliza argumentos de ruta alterna . ^[3] El algoritmo de kernelización actualmente más conocido en términos de 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}$

No es posible, en este problema, encontrar un núcleo de tamaño , a menos que P = NP, ya que dicho núcleo conduciría a un algoritmo de tiempo polinomial para el problema de cobertura de vértices NP-duro. Sin embargo, se pueden demostrar límites mucho más fuertes en el tamaño del núcleo en este caso: a menos que coNP NP/poly (considerado improbable por los teóricos de la complejidad ), 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 improbables 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 debe definirse formalmente la kernelización y existen diferencias sutiles en los usos de esa expresión.

Notación Downey-Fellows

En la notación de Downey & 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 mapea 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á delimitado por una función en . ${\displaystyle k}$

El resultado de la kernelización se denomina kernel. En este contexto general, el tamaño de la cadena se refiere simplemente a su longitud. Algunos autores prefieren utilizar el número de vértices o el número de aristas como medida del tamaño en el contexto de problemas de grafos. ${\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 solo 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}$

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

La kernelización y la manejabilidad con 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 algún c, para generar un núcleo 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. Suponga que la pregunta no es trivial, lo que significa que hay al menos una instancia que está en el lenguaje, llamada , y al menos una instancia que no está en el lenguaje, llamada ; de lo contrario, reemplazar cualquier instancia por la cadena vacía es una kernelización válida. Suponga también que el problema es manejable con parámetros fijos, es decir, tiene un algoritmo que se ejecuta en como máximo pasos en instancias , para alguna constante y alguna función . Para kernelizar una entrada, ejecute este algoritmo en la entrada dada para como máximo pasos. Si termina con una respuesta, use esa respuesta para seleccionar o como el kernel. Si, en cambio, excede el límite en el número de pasos sin terminar, entonces devuélvase a sí mismo como el kernel. Debido a que solo se devuelve como un kernel para entradas con , se deduce que el tamaño del kernel producido de esta manera es como máximo . Este límite de tamaño es computable, suponiendo, a partir de la manejabilidad de parámetros fijos, que 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értices parametrizada por el tamaño de la cobertura de vértices: El problema de cobertura de vértices 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 hipergrafos -uniformes tienen núcleos con aristas 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 núcleos con aristas 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 -path consiste en decidir si un gráfico dado tiene una ruta de longitud al menos . Este problema tiene núcleos de tamaño exponencial en , y no tiene núcleos de tamaño polinomial 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 planares y, más generalmente, en gráficos que excluyen algún gráfico fijo como menor . ^[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 una medida de complejidad estructural de la entrada como el valor del parámetro, lo que lleva a las llamadas parametrizaciones estructurales. Este enfoque es fructífero para instancias cuyo tamaño de solución es grande, pero para las cuales alguna otra medida de complejidad está acotada. Por ejemplo, el número de vértices de retroalimentación de un grafo no dirigido se define como la cardinalidad mínima de un conjunto de vértices cuya eliminación hace acíclico. El problema de cobertura de vértices parametrizado por el número de vértices de retroalimentación del grafo de entrada tiene una kernelización polinomial: ^[9] Hay un algoritmo de tiempo polinomial que, dado un grafo cuyo número de vértice de retroalimentación es , genera un grafo en vértices tales que una cobertura de vértices mínima en se puede transformar en una cobertura de vértices mínima para en tiempo polinomial. Por lo tanto, el algoritmo de kernelización garantiza que las instancias con un pequeño número de vértices de retroalimentación 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}$

Véase también

• Compresión iterativa , una técnica de diseño diferente para algoritmos manejables con 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 y Goldsmith (1993)
2. Flum y Grohe (2006)
3. Flum y Grohe (2006) ofrecen un núcleo basado en la reducción de corona que tiene vértices. El límite de vértices es un poco más complejo 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 otros (2009)
8. Fomin y otros (2010)
9. Jansen y Bodlaender (2013)

Referencias

• Abu-Khzam, Faisal N.; Collins, Rebecca L.; Fellows, Michael R .; Langston, Michael A .; Suters, W. Henry; Symons, Chris T. (2004), Algoritmos de kernelización para el problema de cobertura de vértices: teoría y experimentos (PDF) , Universidad de Tennessee.
• Bodlaender, Hans L. ; Downey, Rod G. ; Fellows, 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), "El no determinismo dentro de ", 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 satisfacibilidad no permite una esparsificación no trivial a menos que la jerarquía de tiempo polinomial colapse" (PDF) , Actas del 42.º Simposio ACM sobre teoría de la computación (STOC 2010) (PDF) , págs. 251–260, doi :10.1145/1806689.1806725, ISBN 978-1-4503-0050-6, Número de identificación del sujeto  1117711.
• Downey, RG ; Fellows, MR (1999), Complejidad parametrizada , Monografías en Ciencias de la Computación, Springer, doi :10.1007/978-1-4612-0515-9, ISBN 0-387-94883-X, MR  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. 503–510.
• Jansen, Bart MP; Bodlaender, Hans L. (2013), "Revisión de la kernelización de cobertura de vértices: límites superior e inferior para un parámetro refinado", Theory Comput. Syst. , 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 un conjunto de vértices de retroalimentación", ACM Transactions on Algorithms , 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.

Lectura adicional

• 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