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 grafos dispersos tienen expansión acotada. Una propiedad estrechamente relacionada pero más fuerte, la expansión polinómica , es equivalente a la existencia de teoremas separadores para estas familias. Las familias con estas propiedades tienen algoritmos eficientes para problemas que incluyen el problema del isomorfismo de subgrafos y la verificación de modelos para la teoría de grafos de primer orden.
Un grafo menor t -superficial de un grafo G se define como un grafo formado a partir de G mediante la contracción de una colección de subgrafos disjuntos en vértices de radio t y la eliminación de los vértices restantes de G. Una familia de grafos tiene expansión acotada si existe una función f tal que, en cada grafo menor t -superficial de un grafo de la familia, la razón de aristas a vértices es como máximo f ( t ). [1]
Las definiciones equivalentes de clases de expansiones acotadas son que todos los menores superficiales tienen un número cromático acotado por una función de t , [1] o que la familia dada tiene un valor acotado de un parámetro topológico . Tal parámetro es un invariante de grafo que es monótono en subgrafos, de modo que el valor del parámetro puede cambiar solo de manera controlada cuando se subdivide un grafo, y de modo que un valor de parámetro acotado implica que un grafo tiene una degeneración acotada . [2]
Una noción más fuerte es la expansión polinómica , lo que significa que la función f utilizada para limitar la densidad de aristas de los menores superficiales es un polinomio . Si una familia de grafos hereditarios obedece a un teorema separador , que establece que cualquier grafo de n vértices en la familia se puede dividir en partes con como máximo n /2 vértices mediante la eliminación de O ( n c ) vértices para alguna constante c < 1, entonces esa familia necesariamente tiene expansión polinómica. Por el contrario, los grafos con expansión polinómica tienen teoremas separadores sublineales. [3]
Debido a la conexión entre separadores y expansión, cada familia de grafos menores cerrados , incluida la familia de grafos planares , tiene expansión polinomial. Lo mismo es cierto para los grafos 1-planares y, más generalmente, los grafos que se pueden incrustar en superficies de género acotado con un número acotado de cruces por arista, así como los grafos de cuerdas libres bicliques , ya que todos estos obedecen teoremas de separadores similares a los grafos planares. [4] [5] [6] [7] En espacios euclidianos de dimensión superior , los grafos de intersección de sistemas de bolas con la propiedad de que cualquier punto del espacio está cubierto por un número acotado de bolas también obedecen teoremas de separadores [8] que implican expansión polinomial.
Aunque los gráficos 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 de Erdős–Rényi , [12] y gráficos de número de cola acotado . [2] [13]
Las instancias del problema de isomorfismo de subgrafos en las que el objetivo es encontrar un grafo objetivo de tamaño acotado, como un subgrafo de un grafo mayor cuyo tamaño no está acotado, pueden resolverse en tiempo lineal cuando el grafo mayor pertenece a una familia de grafos 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 primer orden de grafos . [14] [15]
Para los gráficos de expansión polinomial, existen esquemas de aproximación en tiempo polinomial para el problema de cobertura de conjuntos , el problema del conjunto independiente máximo , el problema del conjunto dominante y varios otros problemas de optimización de gráficos relacionados. [16]