Blackberry (teoría de grafos)

En teoría de grafos, una mora para un grafo no dirigido G es una familia de subgrafos conectados de un grafo G que se tocan entre sí: para cualquier par de subgrafos que no tengan vértices comunes, debe haber una arista cuyos vértices finales se encuentren en estos dos subgrafos. El orden de la mora es el tamaño más pequeño del conjunto de vértices G que tiene una intersección no vacía con cada subgrafo de la mora. Las moras se utilizan para describir el ancho del árbol de un gráfico G [1] .

Ancho de madera y cubierta

Una cobertura de orden k en un grafo G es una función β que lleva todo conjunto X con menos de k vértices a una componente conexa G  −  X de tal manera que dos subconjuntos cualesquiera β ( X ) y β ( Y ) se tocan entre sí . Es decir, las imágenes de β forman una mora de orden k en G. Por el contrario, cualquier mora se puede usar para crear un refugio: por cada conjunto X más pequeño que el orden de la mora, hay un solo componente conectado β ( X ) que contiene todos los subgráficos en la mora que no están conectados a X .

Como han demostrado Seymour y Thomas , el orden de una mora (o, de manera equivalente, un refugio) describe el ancho del árbol:  un gráfico tiene una mora de orden k si y solo si el ancho del árbol es al menos k − 1 [1] .

Tamaño de las moras

Como señalaron Grohe y Marx, los expansores de grados acotados tienen un ancho de árbol proporcional al número de vértices, y para incluir todos los subgrafos que no comparten vértices con todos los subconjuntos de ese tamaño, la mora para dichos gráficos debe contener exponencialmente muchos subgrafos distintos. Más precisamente, para estos gráficos, incluso aquellas moras cuyo orden es ligeramente mayor que la raíz cuadrada del ancho del árbol deben tener un tamaño exponencial. Sin embargo, Groh y Marx también demostraron que cualquier gráfico con un ancho de árbol k tiene una zarza de tamaño y orden polinomial [2] .

Complejidad computacional

Dado que las zarzas pueden tener un tamaño exponencial, no siempre es posible construirlas en tiempo polinomial para gráficos con un ancho de árbol ilimitado. Sin embargo, si el ancho del árbol es limitado, el tiempo de construcción del polinomio es posible; es posible encontrar una mora de orden k , si existe, en el tiempo , donde n  es el número de vértices en el gráfico. Son posibles algoritmos aún más rápidos para gráficos con un pequeño número de separadores mínimos [3] .

Bodlender, Grigoriev y Coster [4] estudiaron algoritmos heurísticos para encontrar moras de alto orden. Sus métodos no siempre dieron moras con un orden cercano al ancho del árbol, pero para gráficos planos dan un factor de aproximación constante . Kreutzer y Tazari [5] proponen algoritmos de búsqueda probabilística en tiempo polinomial sobre grafos con ancho de árbol k zarzas de tamaño y orden polinomial , que corresponde al factor de orden logarítmico derivado por Grohe y Marx ( Grohe, Marx 2009 ) para la existencia de zarzas de polinomio Talla.

Enlaces

1. ↑ 1 2 Paul D. Seymour, Robin Thomas. Búsqueda de gráficos y un teorema min-max para el ancho del árbol // Journal of Combinatorial Theory . - 1993. - T. 58 , núm. 1 . — P. 22–33 . -doi : 10.1006/ jctb.1993.1027 . . En este artículo, las moras se denominan "pantallas" y sus órdenes se denominan "grosor".
2. ↑ Martin Grohe, Daniel Marx. Sobre el ancho del árbol, el tamaño de la zarza y ​​la expansión // Journal of Combinatorial Theory . - 2009. - T. 99 , núm. 1 . — S. 218–228 . -doi : 10.1016/ j.jctb.2008.06.004 . .
3. ↑ Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca. Fundamentos matemáticos de la informática 2009: 34º Simposio internacional, MFCS 2009, Novy Smokovec, High Tatras, Eslovaquia, 24-28 de agosto de 2009, Actas. - Berlín: Springer, 2009. - T. 5734. - S. 223-234. -doi : 10.1007 / 978-3-642-03816-7_20 . .
4. ↑ Bodlaender. Límites inferiores de Treewidth con zarzas. — Algorítmica . - 2008. - T. 51. - S. 81–98. -doi : 10.1007 / s00453-007-9056-z . .
5. ↑ Stephan Kreutzer, Siamak Tazari. Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos (SODA '10). - 2010. - S. 354-364. .