La teoría de la bidimensionalidad caracteriza una amplia gama de problemas de gráficos ( bidimensionales ) que admiten soluciones eficientes aproximadas, de parámetros fijos o kernel en una amplia gama de gráficos. Estas clases de gráficos incluyen gráficos planos , gráficos de mapas, gráficos de género acotado y gráficos que excluyen cualquier menor fijo. En particular, la teoría de la bidimensionalidad se basa en la teoría de grafos menores de Robertson y Seymour ampliando los resultados matemáticos y construyendo nuevas herramientas algorítmicas. La teoría fue introducida en el trabajo de Demaine , Fomin , Hajiaghayi y Thilikos, [1]por lo que los autores recibieron el Premio Nerode en 2015.
Definición
Un problema parametrizado es un subconjunto de para un alfabeto finito . Una instancia de un problema parametrizado consta de (x, k) , donde k se denomina parámetro.
Un problema parametrizado es menor-bidimensional si
- Para cualquier par de gráficos , tal que es menor de y entero , produce que . En otras palabras, contraer o eliminar una arista en un gráficono se puede aumentar el parámetro; y
- hay tal que por cada -red , para cada . En otras palabras, el valor de la solución en debería ser al menos .
Ejemplos de problemas bidimensionales menores son las versiones parametrizadas de cobertura de vértices , conjunto de vértices de retroalimentación , coincidencia mínima máxima y ruta más larga .
Dejar ser el gráfico obtenido de la -rejilla triangulando las caras internas de modo que todos los vértices internos sean de grado 6, y luego una esquina de grado dos unida por aristas con todos los vértices de la cara externa. Un problema parametrizadoes contracción-bidimensional si
- Para cualquier par de gráficos , tal que es una contracción de y entero , produce que . En otras palabras, contraer un borde en un gráficono se puede aumentar el parámetro; y
- hay tal que para cada .
Ejemplos de problemas bidimensionales de contracción son conjunto dominante , conjunto dominante conectado , árbol de expansión de hojas máximas y conjunto dominante de borde .
Teoremas de cuadrícula excluidos
Todas las aplicaciones algorítmicas de bidimensionalidad se basan en la siguiente propiedad combinatoria: o el ancho de árbol de un gráfico es pequeño o el gráfico contiene una cuadrícula grande como menor o contracción. Más precisamente,
- Hay una función f tal que todo gráfico G excluyendo un gráfico h -vertex fijo como menor y de ancho de árbol al menos f (h) r contiene (rxr) -grid como menor. [2]
- Hay una función g tal que cada gráfico G excluyendo un fijo h -vertex ápice gráfico como un menor de edad y de treewidth al menos g (h) r puede ser borde-contratado para. [3]
El teorema de la cuadrícula de Halin es un teorema análogo de la cuadrícula excluida para gráficos infinitos. [4]
Algoritmos parametrizados subexponenciales
Dejar ser un problema bidimensional menor, tal que para cualquier gráfico G excluyendo algún gráfico fijo como menor y de ancho de árbol como máximo t , decidir si se puede hacer a tiempo . Luego, para cada gráfico G, excluyendo algún gráfico fijo como menor, decidir si se puede hacer a tiempo . De manera similar, para problemas bidimensionales de contracción, para el gráfico G excluyendo algún gráfico de vértice fijo como menor, inclusión se puede decidir a tiempo .
Por lo tanto, muchos problemas bidimensionales como la cobertura de vértices, el conjunto dominante, la ruta k, se pueden resolver en el tiempo. en gráficos excluyendo algunos gráficos fijos como menor.
Esquemas de aproximación de tiempo polinomial
La teoría de la bidimensionalidad se ha utilizado para obtener esquemas de aproximación de tiempo polinómico para muchos problemas bidimensionales. Si un problema bidimensional menor (contracción) tiene varias propiedades adicionales [5] [6], entonces el problema plantea esquemas eficientes de aproximación en tiempo polinómico en gráficos (vértice) sin menores.
En particular, haciendo uso de la bidimensionalidad, se demostró que el conjunto de vértices de retroalimentación , la cobertura de vértices , la cobertura de vértices conectados, el empaquetamiento de ciclos, el conjunto de impactos de diamantes, el bosque inducido máximo, el subgrafo bipartito máximo inducido y el subgrafo plano máximo inducido admiten un EPTAS en H gráficos libres de menores. Conjunto dominante de bordes, conjunto dominante, conjunto r-dominante, conjunto dominante conectado, conjunto r-disperso, coincidencia mínima máxima, conjunto independiente , árbol de expansión de grado completo máximo, máximo inducido como máximo subgrafo de grado d, árbol de expansión interno máximo , inducido el emparejamiento , el empaquetamiento de triángulos, el conjunto de dominación r parcial y la cobertura de vértice parcial admiten un EPTAS en gráficos sin vértice-menor.
Kernelización
Se dice que un problema parametrizado con un parámetro k admite un núcleo de vértice lineal si hay una reducción de tiempo polinomial, llamada algoritmo de kernelización , que mapea la instancia de entrada a una instancia equivalente con como máximo O (k) vértices.
Cada problema bidimensional menor con propiedades adicionales, es decir, con la propiedad de separación y con un índice entero finito, tiene un núcleo de vértice lineal en los gráficos excluyendo algunos gráficos fijos como menor. De manera similar, cada problema bidimensional de contraccióncon la propiedad de separación y con un índice entero finito tiene un núcleo de vértice lineal en los gráficos excluyendo algunos gráficos de vértice fijo como menor. [7]
Notas
- ^ Demaine y col. (2005)
- ^ Error de harvtxt de Demaine y Hajiaghayi (2008) : objetivos múltiples (2 ×): CITEREFDemaineHajiaghayi2008 ( ayuda )
- ^ Fomin, Golovach y Thilikos (2009)
- ^ Diestel (2004)
- ^ Fomin y col. (2011)
- ^ Demaine y Hajiaghayi (2005)
- ^ Fomin y col. (2010)
Referencias
- Demaine, Erik D .; Fomin, Fedor V .; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2005), "Algoritmos parametrizados subexponenciales en gráficos de género acotado y gráficos libres de H -minor", J. ACM , 52 (6): 866–893, arXiv : 1104.2230 , doi : 10.1145 / 1101821.1101823 , S2CID 6238832.
- Demaine, Erik D .; Fomin, Fedor V .; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2004), "Parámetros bidimensionales y ancho de árbol local", SIAM Journal on Discrete Mathematics , 18 (3): 501–511, CiteSeerX 10.1.1.81.9021 , doi : 10.1137 / S0895480103433410.
- Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2005), "Bidimensionalidad: nuevas conexiones entre algoritmos FPT y PTAS", 16º Simposio ACM-SIAM sobre algoritmos discretos (SODA 2005) , págs. 590–601.
- Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2008), "Lineality of grid minors in treewidth with applications through bidimensionality", Combinatorica , 28 (1): 19–36, doi : 10.1007 / s00493-008-2140-4 , S2CID 16520181.
- Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2008), "La teoría de la bidimensionalidad y sus aplicaciones algorítmicas", The Computer Journal , 51 (3): 332–337, doi : 10.1093 / comjnl / bxm033 , hdl : 1721.1 / 33090.
- Diestel, R. (2004), "Una prueba breve del teorema de la cuadrícula de Halin", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 74 : 237–242, doi : 10.1007 / BF02941538 , MR 2112834 , S2CID 124603912.
- Fomin, Fedor V .; Golovach, Petr A .; Thilikos, Dimitrios M. (2009), "Contraction Bidimensionality: The Accurate Picture", 17º Simposio Europeo Anual sobre Algoritmos (ESA 2009) , Lecture Notes in Computer Science, 5757 , págs. 706–717, doi : 10.1007 / 978-3 -642-04128-0_63.
- Fomin, Fedor V .; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket (2011), "Bidimensionalidad y EPTAS", Proc. 22º Simposio ACM / SIAM sobre algoritmos discretos (SODA 2011) , págs. 748–759, arXiv : 1005.5449 , Bibcode : 2010arXiv1005.5449F.
- Fomin, Fedor V .; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionality and Kernels", 21º Simposio ACM-SIAM sobre algoritmos discretos (SODA 2010) , págs. 503–510.
Otras lecturas
- Cygan, Marek; Fomin, Fedor V .; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), "Capítulo 7", Algoritmos parametrizados , Springer, p. 612, ISBN 978-3-319-21274-6
- Fomin, Fedor V .; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019), "Capítulo 15", Kernelización: Teoría del preprocesamiento parametrizado , Cambridge University Press, p. 528, doi : 10.1017 / 9781107415157 , ISBN 978-1107057760