En teoría de grafos, una zarza para un grafo no dirigido G es una familia de subgrafos conectados de G que se tocan entre sí: por cada par de subgrafos separados, debe existir un borde en G que tenga un punto final en cada subgrafo. El orden de una zarza es el tamaño más pequeño de un conjunto de golpes , un conjunto de vértices de G que tiene una intersección no vacía con cada uno de los subgráficos. Brambles se pueden utilizar para caracterizar el treewidth de G . [1]
Treewidth y paraísos
Un refugio de orden k en un gráfico G es una función β que asigna cada conjunto X de menos de k vértices a un componente conectado de G - X , de tal manera que cada dos subconjuntos β ( X ) y β ( Y ) se tocan El uno al otro. Así, el conjunto de imágenes de β forma una zarza en G , de orden k . A la inversa, cada zarza puede usarse para determinar un refugio: para cada conjunto X de tamaño más pequeño que el orden de la zarza, hay un componente conectado único β ( X ) que contiene todos los subgrafos de la zarza que están separados de X .
Como mostraron Seymour y Thomas, el orden de una zarza (o equivalentemente, de un refugio) caracteriza el ancho del árbol : un gráfico tiene una zarza de orden k si y solo si tiene un ancho de árbol al menos k - 1 . [1]
Tamaño de las zarzas
Los gráficos de expansión de grado acotado tienen un ancho de árbol proporcional a su número de vértices y, por lo tanto, también tienen zarzas de orden lineal. Sin embargo, como mostraron Martin Grohe y Dániel Marx, para estos gráficos, una zarza de tan alto orden debe incluir exponencialmente muchos conjuntos. Más fuertemente, para estos gráficos, incluso las zarzas cuyo orden es ligeramente mayor que la raíz cuadrada del ancho del árbol deben tener un tamaño exponencial. Sin embargo, Grohe y Marx también demostraron que cada gráfica de ancho de árbol k tiene una zarza de tamaño polinomial y de orden. [2]
Complejidad computacional
Debido a que las zarzas pueden tener un tamaño exponencial, no siempre es posible construirlas en tiempo polinomial para gráficos de ancho de árbol ilimitado. Sin embargo, cuando el ancho del árbol está acotado, es posible una construcción de tiempo polinomial: es posible encontrar una zarza de orden k , cuando existe una, en el tiempo O ( n k + 2 ) donde n es el número de vértices en el gráfico dado. . Son posibles algoritmos aún más rápidos para gráficos con pocos separadores mínimos. [3]
Bodlaender, Grigoriev y Koster [4] estudiaron heurística para encontrar zarzas de alto orden. Sus métodos no siempre generan zarzas de orden cercano al ancho del árbol del gráfico de entrada, pero para los gráficos planos dan una relación de aproximación constante . Kreutzer y Tazari [5] proporcionan algoritmos aleatorios que, en gráficos de ancho de árbol k , encuentran zarzas de tamaño polinómico y de ordendentro del tiempo polinomial, dentro de un factor logarítmico del orden mostrado por Grohe y Marx (2009) para las zarzas de tamaño polinomial.
Zarzas dirigidas
También se ha definido el concepto de zarza para grafos dirigidos. [6] [7] En un gráfico dirigido D , una zarza es una colección de subgrafos fuertemente conectados de D que se tocan entre sí: por cada par de elementos disjuntos X , Y de la zarza, debe existir un arco en D desde X a y y uno de y a X . El orden de una zarza es el tamaño más pequeño de un conjunto de golpes , un conjunto de vértices de D que tiene una intersección no vacía con cada uno de los elementos de la zarza. El número zarza de D es el orden máximo de una zarza en D . El número de zarzas de un gráfico dirigido está dentro de un factor constante de su ancho de árbol dirigido. [8]
Referencias
- ↑ a b Seymour, Paul D .; Thomas, Robin (1993), "Búsqueda de gráficos y un teorema mínimo-máximo para el ancho del árbol", Journal of Combinatorial Theory , Serie B, 58 (1): 22–33, doi : 10.1006 / jctb.1993.1027 , MR 1214888. En esta referencia, las zarzas se denominan "pantallas" y su orden se denomina "grosor".
- ^ Grohe, Martin ; Marx, Dániel (2009), "Sobre el ancho del árbol, el tamaño de las zarzas y la expansión", Journal of Combinatorial Theory , Serie B, 99 (1): 218–228, doi : 10.1016 / j.jctb.2008.06.004 , MR 2467827.
- ^ Chapelle, Mathieu; Mazoit, Frédéric; Todinca, Ioan (2009), "Construyendo zarzas", 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 , Notas de conferencia en Ciencias de la Computación, 5734 , Berlín: Springer, págs. 223–234, Bibcode : 2009LNCS.5734..223C , doi : 10.1007 / 978-3-642-03816-7_20 , MR 2539494.
- ^ Bodlaender, Hans L .; Grigoriev, Alexander; Koster, Arie MCA (2008), "Límites inferiores de ancho de árbol con zarzas", Algorithmica , 51 (1): 81–98, doi : 10.1007 / s00453-007-9056-z , MR 2385750.
- ^ Kreutzer, Stephan; Tazari, Siamak (2010), "Sobre las zarzas, los menores en forma de cuadrícula y la intratabilidad parametrizada de la lógica monádica de segundo orden", Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos (SODA '10) , págs. 354 –364.
- ^ Reed, Bruce (1999), "Introducción al ancho del árbol dirigido", Electronic Notes in Discrete Mathematics , 3 , Elsevier, págs. 222-229, doi : 10.1016 / S1571-0653 (05) 80061-7
- ^ Johnson, Thor; Robertson, Neil; Seymour, Paul; Thomas, Robin (2001), "Directed Tree-Width", Journal of Combinatorial Theory, Serie B , 82 , págs. 138-154, doi : 10.1006 / jctb.2000.2031
- ^ Kawarabayashi, Ken-ichi; Kreutzer, Stephan (2015), "The Directed Grid Theorem", Actas del 47º Simposio Anual de ACM sobre Teoría de la Computación (STOC '15) , Portland, Oregon, EE. UU.: ACM, págs. 655–664, arXiv : 1411.5681 , doi : 10.1145 / 2746539.2746586