Reducción paramétrica

La reducción paramétrica es una técnica para diseñar algoritmos eficientes que logran su eficiencia a través de un paso de preprocesador en el que la entrada del algoritmo se reemplaza por una entrada más pequeña llamada "núcleo". El resultado de resolver el problema en el kernel debe ser el mismo que para los datos iniciales o el resultado de la solución para el kernel debe transformarse fácilmente en el resultado deseado del problema original.

La reducción paramétrica a menudo se logra mediante la aplicación de un conjunto de reglas de reducción que cortan la parte de un problema particular que es fácil de tratar. En la teoría de la complejidad parametrizada , a menudo se puede probar que un kernel con límites garantizados dependiendo del tamaño del kernel (en función de algunos parámetros relacionados con el problema) se puede encontrar en tiempo polinomial . Si es posible, el resultado será un algoritmo decidible paramétricamente fijo cuyo tiempo de ejecución es la suma del paso de reducción paramétrica (tiempo polinómico) y el tiempo (no polinomial pero limitado por parámetros) para resolver el kernel. Además, cualquier problema que pueda resolverse mediante un algoritmo solucionable de parámetros fijos puede resolverse mediante un algoritmo de reducción paramétrica de este tipo.

Ejemplo: cobertura de vértices

Un ejemplo estándar de un algoritmo de reducción paramétrica es la reducción paramétrica del problema de cobertura de vértices de S. Bass [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 máximo que incluye el vértice final de cada gráfico si existe dicho conjunto, o una excepción de error si dicho conjunto no existe. Este problema es NP-difícil . Sin embargo, se pueden utilizar las siguientes reglas para su reducción paramétrica: $GRAMO$ $k$ $k$

Si y es un vértice de grado mayor que , elimínelo del gráfico y disminuya en uno. El problema de cobertura de vértices de cualquier tamaño debe contener , porque de lo contrario se elegirían demasiados de sus vecinos para cubrir los bordes incidentes. Por lo tanto, la cobertura de vértices óptima para el gráfico original se puede formar a partir de la cobertura reducida del problema volviendo a agregar a la cobertura. $k>0$ $v$ $k$ $v$ $k$ $k$ $v$ $v$
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. $v$ $v$
Si quedan más de aristas en el gráfico y no se pueden aplicar las dos reglas anteriores, entonces el gráfico no puede contener una cubierta de vértice de tamaño . Después de eliminar todos los vértices de grado mayor que , cada vértice restante puede cubrir la mayoría de los bordes y el conjunto de vértices puede cubrir la mayoría de los bordes. En este caso, la entrada del problema se puede reemplazar por un gráfico con dos vértices, una arista y el valor , y este problema tampoco tiene solución. $k^{2}$ $k$ $k$ $k$ $k$ $k^{2}$ $k=0$

Un algoritmo que vuelve a aplicar estas reglas hasta que no se puedan realizar más reducciones necesariamente termina con un núcleo que tiene como máximo aristas y (dado que cada arista tiene como máximo dos vértices terminales y ningún vértice aislado) como máximo vértices. Esta reducción paramétrica se puede hacer en tiempo lineal . Una vez que se construye el kernel, el problema de la cobertura de vértices se puede resolver mediante un algoritmo de fuerza bruta , que verifica que cada subconjunto del kernel sea una cobertura del kernel. Así, el problema de la cobertura de vértices se puede resolver a tiempo para un grafo con vértices y aristas, lo que permite resolverlos eficientemente cuando son pequeños, aunque sean grandes . $k^{2}$ ${\ estilo de visualización 2k^{2))$ ${\ estilo de visualización O (2 ^ {2k ^ {2)) + n + m)}$ $norte$ $metro$ $k$ $norte$ $metro$

Aunque este límite se puede resolver de forma paramétrica fija, su dependencia del parámetro es más alta de lo que uno podría desear. Los procedimientos de reducción paramétrica más complejos pueden mejorar este límite al encontrar núcleos más pequeños a costa de más tiempo en el paso de reducción paramétrica. Se conocen algoritmos para el problema de cobertura de vértices de reducción paramétrica, que dan núcleos máximos con vértices. El algoritmo que logra este límite mejorado utiliza la relajación de medio entero del problema de cobertura de vértices mediante un problema de programación lineal según George Nemhauser y Trotter [2] . Otro algoritmo de reducción paramétrica que logra este límite se basa en un truco llamado regla de reducción de corona y utiliza argumentos de alternancia de rutas [3] . En la actualidad, el algoritmo de reducción paramétrica más conocido en cuanto al número de vértices se debe a Lampis [4] y consigue vértices para cualquier constante . $2k$ $2k-c\log k$ $C$

Es imposible para este problema encontrar un kernel de tamaño a menos que P=NP, en cuyo caso el kernel conduciría a un algoritmo polinomial para el problema de cobertura de vértice duro NP. Sin embargo, en este caso se pueden probar límites más estrictos en el tamaño del kernel, a menos que coNP NP/poly (que los teóricos de la complejidad computacional consideran improbable), es imposible encontrar kernels con bordes en tiempo polinomial [5] . ${\ estilo de visualización O (\ log k)}$ $\subseteq$ ${\ estilo de visualización \ épsilon > 0}$ $O(k^{2-\epsilon })$

Definición

No existe un consenso claro en la literatura sobre cómo debe definirse formalmente la reducción paramétrica, y existe una diferencia sutil en el uso de tales expresiones.

Notación de Downey-Fellows

En la notación de Downey-Fellowes [6] , un problema parametrizado es un subconjunto que describe el problema de solución . $L\subseteq \Sigma ^{*}\times \mathbb {N}$

La reducción paramétrica de un problema parametrizado es un algoritmo que toma un representante y lo mapea en el tiempo polinomialmente en y a un representante , de modo que $L$ ${\ estilo de visualización (x, k)}$ $|x|$ $k$ ${\ estilo de visualización (x', k')}$

${\ estilo de visualización (x, k)}$ entra si y solo si entra , $L$ ${\ estilo de visualización (x', k')}$ $L$
el tamaño está limitado por una función computable de $X'$ $F$ $k$
$k'$ limitado a una función computable de . $k$

La salida de la reducción paramétrica se llama kernel. En este contexto general , el tamaño de una cadena a menudo se denomina longitud. Algunos autores prefieren el número de vértices o el número de aristas como el tamaño en el contexto de los problemas de grafos. ${\ estilo de visualización (x', k')}$ $X'$

La designación de Flam es Grohe

En la notación Flam-Grohe [7] , un problema parametrizado consiste en un problema de decisión y una función , la parametrización en sí. El parámetro representativo de la tarea es un número . $L\subseteq \Sigma ^{*}$ $\kappa :\Sigma ^{*}\to \mathbb {N}$ $X$ ${\ estilo de visualización \ kappa (x)}$

La reducción paramétrica para un problema parametrizado es un algoritmo que toma un representante con un parámetro y lo asigna en tiempo polinomial a un representante tal que $L$ $X$ $k$ $y$

$X$ entra si y solo si entra $L$ $y$ $L$
el tamaño está limitado por una función computable de . $y$ $F$ $k$

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

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

La reducibilidad paramétrica y la solucionabilidad paramétrica fija son equivalentes

Un problema es solucionable paramétricamente fijo si y solo si puede reducirse paramétricamente y es solucionable .

Que un problema paramétricamente reducible y solucionable es fijo-paramétricamente solucionable se puede ver a partir de la definición anterior: se invoca un algoritmo de reducción paramétrica que se ejecuta en el tiempo para alguna c para obtener un kernel de tamaño . Luego, el kernel se resuelve mediante un algoritmo que verifica que el problema se pueda resolver. El tiempo de ejecución total 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, bajo el supuesto de que es computable, pero puede calcularse mediante la enumeración de todas las entradas posibles de longitud , se deduce que el problema tiene solución paramétrica fija. ${\ estilo de visualización O (| x | ^ {c})}$ $f(k)$ $g(f(k))+O(|x|^{c})$ $g(n)$ ${\ Displaystyle g (f (k))}$ $f(k)$ ${\ Displaystyle g (f (k))}$ $f(k)$

La prueba en la otra dirección de que un problema solucionable paramétricamente fijo es reducible y solucionable paramétricamente es un poco más difícil. Supongamos que la pregunta no es trivial, lo que significa que hay al menos un representante de la tarea llamado , que pertenece al idioma, y al menos un representante de la tarea, que no pertenece al idioma, llamado . De lo contrario, reemplazar cualquier representante con una cadena vacía es una reducción paramétrica válida. Supongamos también que el problema tiene solución paramétricamente fija, es decir, tiene un algoritmo que funciona como máximo en pasos sobre representantes del problema para alguna constante y alguna función . Para implementar la reducción paramétrica de la entrada, aplicamos el algoritmo en una entrada dada en un máximo de pasos. Si el algoritmo termina con una respuesta, use la respuesta para elegir o como núcleo. Si, en cambio, llegamos al límite del número de pasos sin interrupción, devolvemos la tarea en sí como el núcleo. Dado que se devuelve como kernel de entrada con , se deduce que el tamaño del kernel obtenido de esta forma no supera . El límite de tamaño es computable bajo los supuestos de solucionabilidad paramétrica fija, que es computable. $yo_{sí}$ $yo_{no}$ ${\displaystyle f(k)\cdot |x|^{c))$ ${\ estilo de visualización (x, k)}$ $C$ $f(k)$ ${\ estilo de visualización | x | ^ {c + 1}}$ $yo_{sí}$ $yo_{no}$ ${\ estilo de visualización | x | ^ {c + 1}}$ ${\ estilo de visualización (x, k)}$ ${\ estilo de visualización (x, k)}$ ${\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1))$ ${\displaystyle \max\{|I_{sí}|,|I_{no}|,f(k)\))$ $f(k)$

Otros ejemplos

Cobertura de vértices: el problema de la cobertura de vértices tiene núcleos con vértices y bordes máximos [8] . Además, para cualquier , el problema de la cobertura de vértices no tiene núcleos con aristas, a menos que {coNP} {NP/poly} [5] . El problema de la cobertura de vértices en hipergrafías -homogéneas tiene núcleos con aristas, utilizando el lema del girasol , y no tiene núcleos de tamaño a menos que coNP NP/poly [5] . $2k$ $O(k^{2})$ $\varepsilon >0$ $O(k^{2-\varepsilon})$ $\subseteq$ $d$ $O(k^{d})$ $O(k^{d-\varepsilon})$ $\subseteq$
Conjunto de vértices de corte de ciclo: El problema del conjunto de vértices de corte de ciclo tiene núcleos con vértices y aristas [9] . Además, el problema no tiene núcleos con vértices, a menos que coNP NP/poly [5] . $4k^{2}$ $O(k^{2})$ $O(k^{2-\varepsilon})$ $\subseteq$
k-Path: El problema de k-path consiste en decidir si un gráfico dado tiene una ruta de al menos . Este problema tiene un núcleo de tamaño que depende exponencialmente de , y ningún núcleo de tamaño que depende polinomialmente de , a menos que coNP NP/poly [10] . $k$ $k$ $k$ $\subseteq$
Problemas 2D : muchas versiones parametrizadas de problemas 2D tienen núcleos lineales en gráficos planos y, en general, en gráficos que no contienen algún gráfico fijo como menor [11] .

Véase también

Compresión iterativa , otra técnica para desarrollar algoritmos de resolución paramétrica fija

Notas

↑ Esta observación no publicada se indicó en un artículo de Buss y Goldsmith ( Buss, Goldsmith 1993 )
↑ Flum, Grohe, 2006 .
↑ Flam y Grohe ( Flum, Grohe 2006 ) dan un núcleo basado en la reducción de la corona que tiene vértices. El límite del vértice es un poco más complejo. $3k$ $2k$
↑ Lampis, 2011 .
↑ 1 2 3 4 Dell, van Melkebeek, 2010 .
↑ Downey, Becarios, 1999 .
↑ Flum, Grohe, 2006 , pág. cuatro
↑ Chen, Kanj, Jia, 2001 .
↑ Thomasse, 2010 .
↑ Bodlaender, Downey, Fellows, Hermelin, 2009 .
↑ Fomin, Lokshtanov, Saurabh, Thilikos, 2010 .

Literatura

Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, Chris T. Symons. Algoritmos de kernelización para el problema de cobertura de vértices: teoría y experimentos . — Universidad de Tennessee, 2004.
Hans L. Bodlaender, Rod G. Downey, Michael R. Fellows, Danny Hermelin. Sobre problemas sin núcleos polinómicos // Journal of Computer and System Sciences . - 2009. - T. 75 , núm. 8 _ - S. 423-434 . -doi : 10.1016/ j.jcss.2009.04.001 .
Jonathan F. Buss, Judy Goldsmith. No determinismo dentro de P // SIAM Journal on Computing . - 1993. - T. 22 , núm. 3 . - S. 560-572 . -doi : 10.1137/ 0222038 .
Jianer Chen, Iyad A. Kanj, Weijia Jia. Portada de Vertex: Más observaciones y más mejoras // Journal of Algorithms. - 2001. - T. 41 , núm. 2 . - S. 280-301 . -doi : 10.1006/ jagm.2001.1186 .
Holger Dell, Dieter van Melkebeek. La satisfacibilidad no permite la dispersión no trivial a menos que la jerarquía de tiempo polinomial colapse //Actas del 42º Simposio ACM sobre Teoría de la Computación (STOC 2010) . - 2010. - S. 251-260. -doi : 10.1145/ 1806689.1806725 .
RG Downey, becarios MR. Complejidad parametrizada. - Springer, 1999. - ISBN 0-387-94883-X . -doi : 10.1007 / 978-1-4612-0515-9 .
Jörg Flum, Martin Grohe. Teoría de la Complejidad Parametrizada . - Springer, 2006. - ISBN 978-3-540-29952-3 .
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Bidimensionalidad y núcleos // Actas del 21.º Simposio ACM-SIAM sobre algoritmos discretos (SODA 2010). - 2010. - S. 503-510.
Miguel Lampis. Un núcleo de orden 2 k − c log k para cobertura de vértices // Cartas de procesamiento de información . - 2011. - T. 111 , núm. 23-24 . - S. 1089-1091 . -doi : 10.1016/ j.ipl.2011.09.003 .
Stephan Thomasse. Un núcleo de 4 k 2 para el conjunto de vértices de retroalimentación // Transacciones ACM en algoritmos. - 2010. - T. 6 , núm. 2 .
Rolf Niedermeier. Invitación a algoritmos de parámetros fijos . - Oxford University Press, 2006. - ISBN 0-19-856607-7 . .