En teoría de grafos, se dice que una familia de grafos tiene expansión acotada si todos sus menores superficiales son grafos dispersos . Muchas familias naturales de gráficos dispersos tienen expansión limitada. Una propiedad estrechamente relacionada pero más fuerte, la expansión polinomial , es equivalente a la existencia de teoremas del separador para estas familias. Las familias con estas propiedades tienen algoritmos eficientes para problemas, incluido el problema de isomorfismo de subgrafo y la verificación del modelo para la teoría de grafos de primer orden.
Definición y caracterizaciones equivalentes
A t -shallow menor de un gráfico G se define para ser un gráfico formado a partir de G mediante la contratación de una colección de subgraphs vértice-disjuntos de radio t y eliminación de los vértices restantes de G . Una familia de gráficas tiene expansión acotada si existe una función f tal que, en cada t -shallow menor de una gráfica en la familia, la razón de aristas a vértices es como máximo f ( t ). [1]
Las definiciones equivalentes de clases de expansiones limitadas son que todos los menores superficiales tienen un número cromático limitado por una función de t , [1] o que la familia dada tiene un valor limitado de un parámetro topológico . Dicho parámetro es un gráfico invariante que es monótono al tomar subgráficos, de modo que el valor del parámetro solo puede cambiar de manera controlada cuando se subdivide un gráfico, y tal que un valor de parámetro acotado implica que un gráfico tiene degeneración acotada . [2]
Teoremas del separador y expansión de polinomios
Una noción más fuerte es la expansión polinomial , lo que significa que la función f utilizada para unir la densidad de bordes de los menores poco profundos es un polinomio . Si una familia de grafos hereditarios obedece a un teorema del separador , que establece que cualquier grafo de n -vértices de la familia se puede dividir en partes con un máximo de n / 2 vértices mediante la eliminación de O ( n c ) vértices para alguna constante c <1, entonces esa familia tiene necesariamente expansión polinomial. Por el contrario, los gráficos con expansión de polinomios tienen teoremas del separador sublineal. [3]
Clases de gráficos con expansión acotada
Debido a la conexión entre los separadores y la expansión, cada familia de gráficos cerrados menores , incluida la familia de gráficos planos , tiene expansión polinomial. Lo mismo es cierto para los gráficos 1-planar y, de manera más general, los gráficos que se pueden incrustar en superficies de género acotado con un número limitado de cruces por borde, así como para los gráficos de cuerdas sin biclices , ya que todos obedecen teoremas de separadores similares. a los gráficos planares. [4] [5] [6] [7] En espacios euclidianos de dimensiones superiores , las gráficas de intersección de sistemas de bolas con la propiedad de que cualquier punto del espacio está cubierto por un número limitado de bolas también obedecen a los teoremas del separador [8] que implican polinomios expansión.
Aunque las gráficas de espesor de libro acotado no tienen separadores sublineales, [9] también tienen expansión acotada. [10] Otros gráficos de expansión acotada incluyen gráficos de grado acotado, [11] gráficos aleatorios de grado promedio acotado en el modelo Erdős-Rényi , [12] y gráficos de número de cola acotado . [2] [13]
Aplicaciones algorítmicas
Los casos del problema de isomorfismo de subgrafos en los que el objetivo es encontrar un gráfico objetivo de tamaño acotado, como un subgrafo de un gráfico más grande cuyo tamaño no está acotado, pueden resolverse en tiempo lineal cuando el gráfico más grande pertenece a una familia de gráficos de expansión acotada. Lo mismo es cierto para encontrar camarillas de un tamaño fijo, encontrar conjuntos dominantes de un tamaño fijo o, de manera más general, probar propiedades que pueden expresarse mediante una fórmula de tamaño acotado en la lógica de gráficos de primer orden . [14] [15]
Para los gráficos de la expansión polinómica, existen esquemas de aproximación de tiempo polinomial para el problema de cobertura conjunto , problema máximo conjunto independiente , dominando problema conjunto , y varios otros problemas de optimización gráfica relacionados. [dieciséis]
Referencias
- ^ a b Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "5.5 Clases con expansión acotada", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, 28 , Springer, pp. 104-107, doi : 10.1007 / 978-3-642- 27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
- ^ a b Nešetřil, Jaroslav ; Ossona de Méndez, Patrice ; Wood, David R. (2012), "Caracterizaciones y ejemplos de clases de gráficos con expansión acotada", European Journal of Combinatorics , 33 (3): 350–373, arXiv : 0902.3265 , doi : 10.1016 / j.ejc.2011.09.008 , MR 2864421.
- ^ Dvořák, Zdeněk; Norin, Sergey (2016), "Separadores fuertemente sublineales y expansión polinomial", SIAM Journal on Discrete Mathematics , 30 (2): 1095-1101, arXiv : 1504.04821 , doi : 10.1137 / 15M1017569 , MR 3504982
- ^ Nešetřil y Ossona de Mendez (2012) , 14.2 Número de cruce, págs. 319–321.
- ^ Grigoriev, Alejandro; Bodlaender, Hans L. (2007), "Algoritmos para gráficos incrustables con pocos cruces por borde" , Algorithmica , 49 (1): 1–11, doi : 10.1007 / s00453-007-0010-x , MR 2344391.
- ^ Dujmović, Vida; Eppstein, David ; Wood, David R. (2015), "Género, ancho de árbol y número de cruce local", Proc. 23a Int. Symp. Dibujo gráfico (GD 2015) , arXiv : 1506.04380 , Bibcode : 2015arXiv150604380D.
- ^ Fox, Jacob ; Pach, János (2009), "Un teorema del separador para gráficos de cuerdas y sus aplicaciones", Combinatoria, Probabilidad y Computación , 19 (3): 371, doi : 10.1017 / s0963548309990459.
- ^ Miller, Gary L .; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1997), "Separadores para empaquetaduras de esferas y gráficos de vecinos más cercanos", Journal of the ACM , 44 (1): 1–29, doi : 10.1145 / 256292.256294 , MR 1438463.
- ^ Dujmović, Vida; Sidiropoulos, Anastasios; Madera, David R. (2015), 3-Monótono expansores , arXiv : 1501.05020 , bibcode : 2015arXiv150105020D
- ↑ Nešetřil y Ossona de Mendez (2012) , 14.5 Stack Number, págs. 327–328.
- ^ Nešetřil y Ossona de Mendez (2012) , p. 307.
- ^ Nešetřil y Ossona de Mendez (2012) , 14.1 Gráficos aleatorios (modelo Erdős-Rényi), págs. 314–319.
- ^ Nešetřil y Ossona de Mendez (2012) , págs. 321–327.
- ^ Nešetřil y Ossona de Mendez (2012) , 18.3 El problema del isomorfismo del subgrafo y consultas booleanas, págs. 400–401.
- ^ Dvořák, Zdeněk ; Kráľ, Daniel ; Thomas, Robin (2010), "Decidir propiedades de primer orden para gráficos dispersos", Proc. 51º Simposio Anual de IEEE sobre Fundamentos de las Ciencias de la Computación (FOCS 2010) , IEEE Computer Soc., Los Alamitos, CA, págs. 133-142, MR 3024787.
- ^ Har-Peled, Sariel ; Quanrud, Kent (2015), "Algoritmos de aproximación para gráficos de expansión polinomial y de baja densidad" , Algoritmos - ESA 2015: 23rd Annual European Symposium, Patras, Grecia, 14-16 de septiembre de 2015, Proceedings , Lecture Notes in Computer Science, 9294 , Springer-Verlag, págs. 717–728, arXiv : 1501.00721 , doi : 10.1007 / 978-3-662-48350-3_60.