Bidimensionalidad

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 al ampliar los resultados matemáticos y construir nuevas herramientas algorítmicas. La teoría fue introducida en el trabajo de Demaine , Fomin , Hajiaghayi y Thilikos, ^[1] por el cual los autores recibieron el Premio Nerode en 2015.

Definición

Un problema parametrizado es un subconjunto de algún alfabeto finito . Una instancia de un problema parametrizado consta de (x,k) , donde k se denomina parámetro. ${\displaystyle \Pi }$ ${\displaystyle \Gamma ^{*}\times \mathbb {N} }$ ${\displaystyle \Gamma }$

Un problema parametrizado es bidimensional menor si ${\displaystyle \Pi }$

1. Para cualquier par de gráficos , tales que sean menores de y enteros , se obtiene eso . En otras palabras, contraer o eliminar una arista en un gráfico no puede aumentar el parámetro; y ${\displaystyle H,G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle (G,k)\in \Pi }$ ${\displaystyle (H,k)\in \Pi }$ ${\displaystyle G}$
2. existe tal que para cada -grid , para cada . En otras palabras, el valor de la solución debe ser al menos . ${\displaystyle \delta >0}$ ${\displaystyle (r\times r)}$ ${\displaystyle R}$ ${\displaystyle (R,k)\not \in \Pi }$ ${\displaystyle k\leq \delta r^{2}}$ ${\displaystyle R}$ ${\displaystyle \delta r^{2}}$

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 .

Grafico ${\displaystyle \Gamma _{6}}$

Sea el gráfico obtenido de la cuadrícula triangulando 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 parametrizado es contracción bidimensional si ${\displaystyle \Gamma _{r}}$ ${\displaystyle (r\times r)}$ ${\displaystyle \Pi }$

1. Para cualquier par de gráficos , tal que sea una contracción de y un número entero , se obtiene eso . En otras palabras, contraer una arista en un gráfico no puede aumentar el parámetro; y ${\displaystyle H,G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle (G,k)\in \Pi }$ ${\displaystyle (H,k)\in \Pi }$ ${\displaystyle G}$
2. hay tal que para cada . ${\displaystyle \delta >0}$ ${\displaystyle (\Gamma _{r},k)\not \in \Pi }$ ${\displaystyle k\leq \delta r^{2}}$

Ejemplos de problemas bidimensionales de contracción son el conjunto dominante , el conjunto dominante conectado , el árbol de expansión de hojas máximas y el conjunto dominante de aristas .

Teoremas de cuadrícula excluidos

Todas las aplicaciones algorítmicas de bidimensionalidad se basan en la siguiente propiedad combinatoria: o el ancho del á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,

1. Existe una función f tal que cada gráfico G excluyendo un gráfico h fijo de vértice como menor y de ancho de árbol al menos f(h)r contiene (rxr) -grid como menor. ^[2]
2. Existe una función g tal que cada gráfico G , excluyendo un gráfico de vértice h fijo como menor y de ancho de árbol al menos g (h) r, puede contraerse por borde a . ^[3] ${\displaystyle \Gamma _{r}}$

El teorema de la cuadrícula de Halin es un teorema de cuadrícula excluido análogo para gráficos infinitos. ^[4]

Algoritmos parametrizados subexponenciales

Sea 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, decida si se puede hacer a tiempo . De manera similar, para problemas bidimensionales de contracción, para el gráfico G que excluye algún gráfico de vértice fijo como menor, la inclusión se puede decidir en el tiempo . ${\displaystyle \Pi }$ ${\displaystyle (G,k)\in \Pi }$ ${\displaystyle 2^{O(t)}\cdot |G|^{O(1)}}$ ${\displaystyle (G,k)\in \Pi }$ ${\displaystyle 2^{O({\sqrt {k}})}\cdot |G|^{O(1)}}$ ${\displaystyle (G,k)\in \Pi }$ ${\displaystyle 2^{O({\sqrt {k}})}\cdot |G|^{O(1)}}$

Por lo tanto, muchos problemas bidimensionales como Vertex Cover, Dominating Set, k-Path, se pueden resolver en el tiempo en gráficos excluyendo algún gráfico fijo como menor. ${\displaystyle 2^{O({\sqrt {k}})}\cdot |G|^{O(1)}}$

Esquemas de aproximación de tiempo polinomial.

La teoría de la bidimensionalidad se ha utilizado para obtener esquemas de aproximación en tiempo polinomial 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 polinomial en gráficos libres de menores (ápice).

En particular, al hacer 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 conectada, el empaquetamiento de ciclos, el conjunto de impactos de diamantes, el bosque inducido máximo, el subgrafo bipartito inducido máximo y el subgrafo plano inducido máximo admiten un EPTAS en H- gráficos libres de menores. Conjunto dominante de borde, conjunto dominante , conjunto dominante r, conjunto dominante conectado, conjunto disperso r, coincidencia máxima mínima, conjunto independiente , árbol de expansión máximo de grado completo, máximo inducido como máximo subgrafo de grado d, árbol de expansión interno máximo, inducido la coincidencia , el empaquetamiento de triángulos, el conjunto dominante de r parcial y la cobertura de vértices parcial admiten un EPTAS en gráficos sin vértices menores.

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 asigna la instancia de entrada a una instancia equivalente con como máximo O(k) vértices.

Todo problema bidimensional menor con propiedades adicionales, es decir, con la propiedad de separación y con índice entero finito, tiene un núcleo de vértice lineal en los gráficos que excluyen algún gráfico fijo como menor. De manera similar, cada problema bidimensional de contracción 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 algún gráfico de vértice fijo como menor. ^[7] ${\displaystyle \Pi }$ ${\displaystyle \Pi }$

Notas

1. Demaine y col. (2005)
2. Demaine y Hajiaghayi (2008a)   ^{[ se necesita aclaración ]}
3. Fomin, Golovach y Thilikos (2009)
4. Diéstel (2004)
5. Fomín y col. (2011)
6. Demaine y Hajiaghayi (2005)
7. Fomín y col. (2010)

Referencias

• Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2005), "Algoritmos parametrizados subexponenciales en gráficos de género acotado y gráficos libres de H ", J. ACM , 52 (6): 866–893, arXiv : 1104.2230 , doi : 10.1145/1101821.1101823, S2CID  6238832.
• Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2004), "Parámetros bidimensionales y ancho de árbol local", Revista SIAM de Matemáticas Discretas , 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..
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2008a), "Linealidad de cuadrículas menores en ancho de árbol con aplicaciones mediante bidimensionalidad", Combinatorica , 28 (1): 19–36, doi :10.1007/s00493-008-2140-4, S2CID  16520181.
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2008b), "La teoría de la bidimensionalidad y sus aplicaciones algorítmicas", The Computer Journal , 51 (3): 292–302, doi :10.1093/comjnl/bxm033, hdl : 1721.1/33090.
• Diestel, R. (2004), "Una breve demostración 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, vol. 5757, págs. 706–717, doi :10.1007/978-3-642-04128-0_63, ISBN 978-3-642-04127-3.
• 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), "Bidimensionalidad y núcleos", 21º Simposio ACM-SIAM sobre algoritmos discretos (SODA 2010) , págs..

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