Bidimensionalidad

La teoría de la bidimensionalidad caracteriza una amplia gama de problemas de grafos ( bidimensionales ) que admiten soluciones aproximadas, de parámetros fijos o de núcleo eficientes en una amplia gama de grafos. Estas clases de grafos incluyen grafos planares , grafos de mapa, grafos de género acotado y grafos 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 extender 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 un alfabeto finito . Una instancia de un problema parametrizado consiste en (x,k) , donde k se denomina parámetro. ${\displaystyle \Pi }$ ${\displaystyle \Gamma ^{*}\times \mathbb {N} }$ ${\displaystyle \Gamma }$

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

1. Para cualquier par de grafos , tal que sea un menor de y entero , se obtiene que . En otras palabras, contraer o eliminar una arista en un grafo 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 en 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 .

Gráfico ${\displaystyle \Gamma _{6}}$

Sea el grafo obtenido a partir de la cuadrícula triangulando las caras internas de manera que todos los vértices internos sean de grado 6, y luego una esquina de grado dos se una por aristas con todos los vértices de la cara externa. Un problema parametrizado es de contracción bidimensional si ${\displaystyle \Gamma _{r}}$ ${\displaystyle (r\times r)}$ ${\displaystyle \Pi }$

1. Para cualquier par de grafos , tal que sea una contracción de y entero , se obtiene que . En otras palabras, contraer una arista en un grafo 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 conexo , el árbol de expansión de máxima hoja y el conjunto dominante de aristas .

Teoremas de cuadrícula excluidos

Todas las aplicaciones algorítmicas de la bidimensionalidad se basan en la siguiente propiedad combinatoria: o bien el ancho del árbol de un grafo es pequeño, o bien el grafo contiene una cuadrícula grande como menor o contracción. Más precisamente,

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

El teorema de 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 grafo G excluyendo algún grafo fijo como menor y de ancho de árbol como máximo t , decidir si se puede hacer en tiempo . Luego, para cada grafo G excluyendo algún grafo fijo como menor, decidir si se puede hacer en tiempo . De manera similar, para problemas bidimensionales de contracción, para el grafo G excluyendo algún grafo de vértice fijo como menor, la inclusión se puede decidir en 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 cobertura de vértices, conjunto dominante y k-trayectoria 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 de aproximación en tiempo polinomial eficientes en grafos menores libres (ápice).

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 conectada, el empaquetamiento cíclico, el conjunto de impacto de diamante, el bosque inducido máximo, el subgrafo bipartito inducido máximo y el subgrafo planar inducido máximo admiten un EPTAS en grafos libres de H menores. Conjunto de aristas dominantes, conjunto dominante , conjunto r-dominante, conjunto dominante conectado, conjunto r-disperso, coincidencia máxima mínima, conjunto independiente , árbol de expansión de grado completo máximo, subgrafo inducido máximo como máximo de grado d, árbol de expansión interno máximo, coincidencia inducida , empaquetamiento triangular, conjunto r-dominante parcial y cobertura de vértices parcial admiten un EPTAS en grafos libres de ápice menor.

Kernelización

Se dice que un problema parametrizado con un parámetro k admite un núcleo de vértice lineal si existe 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, a saber, con la propiedad de separación y con índice entero finito, tiene un núcleo de vértice lineal en grafos que excluyen algún grafo fijo como menor. De manera similar, todo problema bidimensional de contracción con la propiedad de separación y con índice entero finito tiene un núcleo de vértice lineal en grafos que excluyen algún grafo de vértice fijo como menor. ^[7] ${\displaystyle \Pi }$ ${\displaystyle \Pi }$

Notas

1. Demaine y otros (2005)
2. Demaine y Hajiaghayi (2008a)   ^{[ se necesita aclaración ]}
3. Fomin, Golovach y Thilikos (2009)
4. Diestel (2004)
5. Fomin y otros (2011)
6. Demaine y Hajiaghayi (2005)
7. Fomin y otros (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, 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 (2008a), "Linealidad de los menores de cuadrícula en el ancho del árbol con aplicaciones a través de la 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), "Bidimensionalidad de la contracción: la imagen precisa", 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", Actas del 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. 503–510.

Lectura adicional

• 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ág. 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ág. 528, doi :10.1017/9781107415157, ISBN 978-1107057760