Teorema de la partición plana

El teorema de la partición plana  es una forma de desigualdad isoperimétrica para gráficos planos , que establece que cualquier gráfico plano se puede dividir en partes más pequeñas eliminando una pequeña cantidad de vértices. En particular, al eliminar los vértices O(√ n ) de un gráfico con n vértices (aquí O significa "O grande" ), se puede dividir el gráfico en subgráficos desconectados , cada uno de los cuales tiene como máximo 2 n /3 vértices.

Ungar ( Ungar 1951 ) demostró un teorema de partición plana más débil con vértices O(√ n  log  n ) en el separador en lugar de O(√ n ) , y primero se demostró un teorema con un límite asintótico más fuerte en el tamaño del separador por Lipton y Tarjan ( Lipton y Tarjan 1979). ). Desde sus artículos, el teorema de la partición plana se ha vuelto a demostrar de varias maneras diferentes y se ha mejorado la constante O(√ n ) en el enunciado del teorema. El teorema también se ha extendido a algunas clases de grafos no planos.

Volver a aplicar el teorema de partición produce una jerarquía de separadores, que puede tomar la forma de una descomposición de árbol o una descomposición de gráfico de rama . La jerarquía de separadores se puede usar para desarrollar algoritmos eficientes de " Divide y vencerás" para gráficos planos, y la programación dinámica en estas jerarquías se puede usar para desarrollar resolubles de tiempo exponencial y parámetros fijos para resolver problemas de optimización NP-hard en estos gráficos. La jerarquía de separadores también se puede usar en la disección anidada , una variante eficiente de la eliminación gaussiana para resolver sistemas dispersos de ecuaciones algebraicas lineales que surgen en el método de elementos finitos .

La teoría de la bidimensionalidad Eric Demain , Fedor Fomin, Mohammed Hadjigaya y Dimitros Tilikos generaliza y expande significativamente el alcance del teorema de partición plana a un vasto conjunto de problemas en grafos planos y, más generalmente, en grafos que no no contener un determinado menor .

Enunciado del teorema

En su formulación habitual, el teorema de la partición plana establece que en cualquier gráfico plano G  = ( V , E ) con n vértices, existe una partición de los vértices de G en tres conjuntos A , S y B tales que cada uno de los conjuntos A y B tiene un máximo de 2 n /3 vértices, S tiene O(√ n ) vértices y no hay aristas que tengan un extremo en A y el otro en B . No se requiere que A o B sean subgrafos conectados de G. El conjunto S se llama separador de esta partición.

Una formulación equivalente es que las aristas de cualquier grafo plano G con n vértices se pueden dividir en dos subgrafos G 1 y G 2 no conectados por aristas de tal manera que ambos subgrafos tengan al menos n /3 vértices, mientras que la intersección de los Los conjuntos de vértices de estos dos subgrafos tienen vértices O(√ n ). Tal división se conoce como división [1] . Si se da una desconexión, la intersección de conjuntos de vértices forma un separador, y los vértices que pertenecen a un subgrafo pero no a otro forman dos subconjuntos con no más de 2 n /3 vértices. Por el contrario, si se da una partición en tres conjuntos A , S y B que satisfaga las condiciones del teorema de partición plana, entonces se puede formar una desconexión en la que las aristas con extremos en A pertenecen a G 1 , las aristas con extremos en B pertenecen a G 2 , y las aristas restantes (con ambos extremos en S ) pueden incluirse en cualquiera de los conjuntos.

La constante 2/3 en el enunciado del teorema es arbitraria y se puede reemplazar por cualquier otro número del intervalo abierto (1/2,1) sin cambiar la forma del teorema: se puede dividir en subconjuntos de tamaño más igual obtenido a partir de particiones menos idénticas al volver a particionar un conjunto más grande en partes desiguales y reorganizaciones de los componentes conectados resultantes [2] .

Ejemplo

Considere una red con r filas y c columnas. El número n de vértices de esta red es igual a rc . Por ejemplo, en la figura, r  = 5, c  = 8 y n  = 40. Si r es impar, hay una sola fila central, de lo contrario, hay dos filas igualmente cerca del centro. De manera similar, si c es impar, hay una sola columna central; de lo contrario, hay dos columnas equidistantes del centro. Eligiendo estas filas y columnas centrales como S y eliminando S del gráfico, dividimos el gráfico en dos subgráficos conectados más pequeños A y B , cada uno de los cuales tiene como máximo n /2 vértices. Si r  ≤  c (como en la figura), elegir la columna central dará un separador S con r  ≤ √ n vértices y, de manera similar, si c  ≤  r , elegir la fila central dará un separador con √ n vértices como máximo. Así, cualquier grafo reticular tiene un separador S con como máximo √ n vértices, cuya eliminación divide el grafo en dos componentes conectadas, cuyo tamaño no excede n /2 [3] .

El teorema de la partición plana establece que se puede construir una partición similar para cualquier gráfico plano. El caso de un gráfico plano arbitrario se diferencia del gráfico de red en que en este caso el separador tiene tamaño O(√ n ), que puede ser mayor que el número √ n , y los tamaños de dos subconjuntos A y B (en la mayoría versión común del teorema) no excedan 2 n /3, no n /2, como en los gráficos de red. Además, los subconjuntos A y B no necesariamente forman subgrafos conectados.

Edificios

Paquete

Lipton y Tarjan [4] amplían un gráfico plano dado agregando bordes si es necesario, de modo que se convierta en un gráfico plano máximo (cada cara de una incrustación plana es un triángulo). Luego hacen una búsqueda primero en amplitud comenzando en un vértice arbitrario v y dividen los vértices en niveles según su distancia de v . Si l 1 es una mediana (un nivel para el cual el número de vértices por encima y por debajo no excede n /2), entonces debe haber niveles l 0 y l 2 que sean O(√ n ) pasos por encima y por debajo de l 1 que contiene O (√ n ) vértices, de lo contrario hay más de n vértices cerca del nivel l 1 . Demostraron que debe haber un separador S formado por la unión de l 0 y l 2 y los extremos de las aristas del gráfico G que se encuentran entre estos dos niveles. El tamaño del separador S construido de esta manera no excede √8√ n , que es aproximadamente 2.83√ n . Los vértices del separador y dos conjuntos de particiones se pueden encontrar en tiempo lineal .

Esta prueba del teorema de partición plana también se aplica a gráficos planos ponderados cuando cada vértice tiene un costo no negativo. El gráfico se puede dividir en tres conjuntos A , S y B , de modo que A y B cuesten como máximo 2/3 del precio total, y S tiene O(√ n ) vértices sin bordes de A a B [4] . Al analizar con más cuidado tales construcciones de separadores, Dzhidzhev [2] demostró que el límite de tamaño S se puede reducir a √6√ n , que es aproximadamente igual a 2,45√ n .

Holzer, Schultz Wagner, Prasinos y Zaroligis [5] propusieron una versión simplificada del enfoque: expanden el gráfico a un gráfico plano máximo y realizan una búsqueda en amplitud de la misma manera que se describe anteriormente. Luego, para cada arista e que no pertenece al árbol de búsqueda, forman un bucle combinando e con caminos en el árbol que conectan los extremos de la arista. Luego usan uno de estos bucles como separador de vértices. Aunque este enfoque no garantiza encontrar un separador pequeño para gráficos planos de gran diámetro, sus experimentos muestran que este enfoque funciona mejor que los métodos de fibración de Lipton-Tarjan y Didzhev en muchos tipos de gráficos planos.

Ciclos de separación simples

Para un gráfico que ya es plano máximo, se puede mostrar una construcción rigurosa de un ciclo-separador simple , un ciclo de pequeña longitud cuyas partes interior y exterior (para una incrustación plana particular) no tienen más de 2n /3 vértices. Miller [6] probó esto (con un separador de tamaño √8√ n ) utilizando la técnica de Lipton-Tarjan para una versión modificada de búsqueda en amplitud en la que los niveles forman ciclos simples.

Alon, Seymour y Thomas [7] demostraron la existencia de un separador de ciclos simple de una manera más directa: consideraron ciclos C con como máximo √8√ n vértices que tienen como máximo 2 n /3 vértices fuera de C , luego formaron una partición en tantas partes más cercanas como sea posible dentro y fuera del bucle. Demostraron que bajo todas estas condiciones C necesitaría ser un separador. De lo contrario, las distancias dentro de C deben ser iguales a las distancias en el disco encerrado por C (el camino más corto a través del interior del disco formaría parte de la mejor frontera del ciclo). Además, el ciclo C debe tener una longitud exactamente √8√ n , de lo contrario se puede mejorar reemplazando uno de los lados con los otros dos lados del triángulo. Si los vértices del ciclo C están numerados (en el sentido de las agujas del reloj) de 1 a √8√ n y el vértice i corresponde al vértice √8√ n − i + 1 , entonces estos pares de vértices pueden estar conectados por caminos que no se cortan dentro el disco (según una de las formas del teorema de Menger para grafos planos). Sin embargo, la longitud total de estos caminos excedería n , una contradicción. Después de algunos cálculos adicionales, demostraron, utilizando métodos similares, que existe un separador de ciclo simple de tamaño máximo (3/√2)√ n , que es aproximadamente igual a 2,12√ n .

Jijev y Venkatesan [8] luego mejoraron la constante en el teorema del separador de ciclo simple a 1.97√ n . Su método también permite buscar separadores de ciclos simples para gráficos con pesos de vértices no negativos con un tamaño de separador que no exceda 2√ n . Sin embargo, el método le permite crear separadores con un tamaño más pequeño debido a la mayor diferencia en los tamaños de las partes de la partición. En un gráfico plano no máximo conectado en 2, hay un ciclo separador simple con un tamaño proporcional a la norma euclidiana del vector de longitud de cara, que se puede encontrar en un tiempo casi lineal [9] .

Separadores de ciclo

De acuerdo con el teorema de empaquetamiento de círculos de Koebe-Andreev-Thurston, cualquier gráfico plano se puede representar como un empaquetamiento de círculos en un plano con regiones interiores que no se intersecan, de modo que dos vértices del gráfico son adyacentes si y solo si los círculos correspondientes se tocan. . Como demostraron Miller, Teng, Thurston y Wawasis [10] , para tales empaques hay un círculo que se toca o se encuentra dentro de él, no más de 3 n /4 discos, no más de 3 n /4 discos se encuentran fuera del círculo, o tocarlo, y que interseca discos O(√ n ).

Para probar esto, Miller y otros utilizaron proyección estereográfica para mapear el empaque en la superficie de una sola esfera 3D. Con una elección cuidadosa de la proyección, el centro de la esfera se puede colocar en el punto medio de los centros de los discos de la superficie, de modo que cualquier plano que pase por el centro de la esfera dividirá la esfera en dos hemisferios, cada uno de los cuales contiene o intersecta no más de 3 n /4 discos. Si el plano que pasa por el centro se elige aleatoria y uniformemente, el disco se cortará con una probabilidad proporcional al radio. Así, el número esperado de discos cruzados es proporcional a la suma de los radios de los discos. Sin embargo, la suma de los radios al cuadrado es proporcional al área total de los discos, que no supera el área superficial de una unidad de esfera, una constante. Los argumentos que usan la desigualdad de Jensen muestran que si la suma de los cuadrados de n números no negativos está limitada por una constante, la suma de los números mismos no excede O(√ n ). Por lo tanto, la expectativa del número de intersecciones de discos por un plano aleatorio es O(√ n ) y hay un plano que interseca no más que este número de discos. Este plano interseca a la esfera en un gran círculo , cuya proyección hacia atrás sobre el plano da las propiedades deseadas. Los discos O(√ n ) intersecados por este círculo corresponden a los vértices del separador gráfico planar, que separa los vértices cuyos discos se encuentran dentro del círculo de los vértices cuyos discos se encuentran fuera del círculo, y cada uno de estos subconjuntos tiene como máximo 3 n /4 vértices [10] [11] .

Este método conduce a un algoritmo probabilístico que encuentra un separador en el tiempo lineal [10] y un algoritmo determinista menos práctico con el mismo límite de tiempo lineal [12] . Al analizar cuidadosamente este algoritmo y usar los límites conocidos en la densidad de empaquetamiento de los círculos , se puede demostrar que es posible encontrar separadores que no superen el tamaño

[13]

Aunque este tamaño de separador mejorado da como resultado una partición más desigual del gráfico, Shpilman y Teng [14] argumentan que el método brinda un multiplicador mejorado en el tiempo de ejecución para la partición anidada en comparación con el separador de Alon, Seymour y Thomas [1] . En la práctica, el tamaño de los separadores puede mejorarse utilizando una distribución no uniforme de planos de corte aleatorios [15] .

La proyección estereográfica en el argumento de Miller y otros puede evitarse considerando el círculo más pequeño que contiene una fracción constante de centros de disco, y luego expandiéndose en una cantidad elegida uniformemente en el intervalo [1,2]. Es fácil mostrar, como en Miller, que los discos atravesados ​​por un círculo de este tipo forman un separador regular, y luego la expectativa matemática del número de intersecciones dará el resultado correcto. Es cierto que las constantes resultantes serán algo peores [16] .

Particionamiento espectral

Los métodos de agrupamiento espectral , en los que los vértices de los gráficos se agrupan de acuerdo con las coordenadas de valor propio de las matrices obtenidas del gráfico, se han utilizado durante mucho tiempo como métodos heurísticos para resolver problemas de partición de gráficos para gráficos no planos [17] [18] . Como han demostrado Shpilman y Teng [19] , el agrupamiento espectral también se puede utilizar para probar alternativamente una forma debilitada del teorema de partición plana aplicado a grafos planos con grado de vértice acotado. En su método, los vértices de un gráfico plano dado se clasifican por la segunda coordenada de los vectores propios de la matriz de Kirchhoff del gráfico, y este orden se divide en un punto que minimiza la relación entre el número de aristas eliminadas y el número de vértices de la parte menor del tabique. Como demostraron, cualquier gráfico plano con un grado acotado de vértices tiene una partición en la que esta relación es O(1/√ n ). Aunque es posible que esta partición no esté equilibrada, repetir la partición de la mayor de las dos partes y fusionar los cortes obtenidos en cada iteración finalmente da como resultado una partición equilibrada con bordes O(√ n ). Los vértices finales de estos bordes forman un separador de tamaño (√ n ).

Separadores de costillas

Una variante del teorema de descomposición plana habla de separadores de aristas, pequeños conjuntos de aristas que forman un corte entre dos subconjuntos A y B de los vértices de un grafo. Los dos conjuntos, A y B , deben tener un tamaño como máximo una fracción constante del número n de vértices en el gráfico (por lo general, se requiere que ambos conjuntos sean no mayores de 2 n /3), y cada vértice del gráfico pertenece solo a A o B. El separador consta de aristas que tienen un extremo en A y el otro extremo en B. Los límites de tamaño del separador de bordes dependen tanto del grado de los vértices del gráfico como del número de vértices en el gráfico - gráficos planos, en los que un vértice tiene un grado n  − 1, donde caen las ruedas y las estrellas , no tiene un separador con un sublineal número de aristas, ya que cualquier separador de aristas debe incluir todas las aristas que conectan un vértice de alto grado con los vértices del otro lado del corte. Sin embargo, cualquier gráfico plano con grado máximo Δ tiene un separador de borde de tamaño O(√(Δ n )) [20]

Un separador de ciclo simple en el gráfico dual de un gráfico plano forma un separador de borde del gráfico original [6] [9] . La aplicación del teorema del separador de ciclo simple de Gacit y Miller [9] al gráfico dual de un gráfico plano dado fortalece la estimación de O(√(Δ n )) para el tamaño del separador de bordes, ya que muestra que cualquier gráfico plano tiene un separador de bordes cuyo tamaño es proporcional a la norma euclidiana de los grados de vértice del vector del gráfico.

Papadimitrou y Sideri [21] describieron un algoritmo de tiempo polinomial para encontrar un separador de bordes que divida un gráfico G en dos subgráficos de igual tamaño si G es un subgráfico generado de un gráfico reticular sin agujeros o con un número constante de agujeros. Sin embargo, conjeturaron que el problema es NP-completo para el caso de gráficos planos arbitrarios y demostraron que la complejidad del problema para gráficos de celosía con un número arbitrario de agujeros es la misma que para gráficos planos arbitrarios.

Límites inferiores

En el gráfico de red √ n  × √ n , el conjunto S que contiene s  < √ n puntos puede rodear un subconjunto de como máximo s ( s  − 1)/2 puntos de la red, y el máximo se logra colocando S en la diagonal línea más cerca de la esquina de la red. Así, para formar un separador que separe al menos n /3 puntos de la cuadrícula, s debe tener un tamaño de al menos √(2 n /3), que es aproximadamente 0,82√ n .

Hay gráficos planos con n vértices (para valores arbitrariamente grandes de n ) tales que para cualquier separador S que divide el gráfico restante en subgráficos con un máximo de 2n /3 vértices, S tiene al menos √(4π√3)√ n vértices, aproximadamente 1.56√ n [2] . La construcción utiliza una aproximación de una esfera por un poliedro convexo reemplazando cada cara del poliedro con una malla triangular. Luego se aplica el teorema isoperimétrico a la superficie de una esfera.

Jerarquías de separadores

Los separadores se pueden combinar en una jerarquía de separadores de gráficos planos , una descomposición recursiva en gráficos más pequeños. La jerarquía de separadores se puede representar como un árbol binario , en el que la raíz representa el propio gráfico y los dos nodos secundarios de la raíz son las raíces de los subgráficos generados de los subconjuntos A y B de la jerarquía de separadores construida recursivamente.

La jerarquía de separadores de este tipo forma la base para una descomposición en árbol de un grafo dado, en el que el conjunto de vértices asociados a un nodo del árbol es la unión de los separadores en el camino desde ese nodo hasta la raíz del árbol. Dado que los tamaños de los gráficos disminuyen por un factor constante en cada nivel del árbol, los límites superiores del tamaño de los separadores también disminuyen por un factor constante en cada nivel, de modo que los tamaños de los separadores a lo largo de estos caminos suman exponencialmente a O(√n ) . Es decir, el separador así formado tiene un ancho O(√ n ) y esto se puede usar para mostrar que cualquier gráfico plano tiene un ancho de árbol O(√ n ).

Construir una jerarquía de separadores directamente atravesando el árbol binario de arriba a abajo y aplicando un algoritmo de tiempo lineal para encontrar un separador plano para cada uno de los subgráficos generados asociados con cada nodo del árbol binario tomaría un tiempo total O( n  log  n ) . Sin embargo, es posible construir toda la jerarquía de separadores en tiempo lineal si usamos el enfoque de fibración de amplitud de Lipton-Tarjan y usamos estructuras de datos adecuadas para implementar cada paso de partición en tiempo sublineal [22] .

Si formamos jerarquías basadas no en separadores, sino en desconexiones, en las que dos vértices secundarios se convierten en raíces para la construcción recursiva de jerarquías separadoras para dos subgrafos G 1 y G 2 de la separación de un gráfico dado, entonces la estructura completa forma una descomposición del gráfico en ramas , y no una descomposición en árbol. El ancho de cualquier división en esta descomposición está nuevamente acotado por la suma de los tamaños de los separadores en el camino desde cualquier nodo hasta la raíz de la jerarquía, de modo que cualquier descomposición así obtenida tiene un ancho O(√ n ) y cualquier gráfico plano tiene ancho de rama O(√ n ). Aunque muchos otros problemas de partición de gráficos relacionados son NP-completos incluso para gráficos planos, es posible encontrar una descomposición de un gráfico plano en ramas con un ancho mínimo en tiempo polinomial [23] .

Fomin y Tilikos [24] aplicaron los métodos de Alon, Seymour y Thomas [7] más directamente para construir una descomposición de un gráfico en ramas, y demostraron que cualquier gráfico plano tiene un ancho de ramificación que no excede 2.12√ n , es decir, con la misma constante en cuanto al teorema de partición de Alon Alon, Seymour y Thomas por separadores de ciclo simple. Dado que el ancho del árbol de cualquier gráfico es como máximo 3/2 del ancho de la rama, esto también muestra que los gráficos planos tienen un ancho de árbol como máximo de 3,18√ n .

Otras clases de grafos

Algunos gráficos dispersos no tienen separadores de tamaño sublineales: en un expansor , eliminar una fracción constante de vértices deja un componente conectado [4] [25] .

Quizás el teorema de partición más antiguo es el resultado de Jordan [26] de que cualquier árbol se puede dividir en dos subárboles con un máximo de n /2 vértices en cada uno eliminando un solo vértice [10] . En particular, el vértice que minimiza el tamaño del componente máximo tiene esta propiedad. Aplicando la misma técnica a la descomposición en árbol de un gráfico arbitrario, se puede demostrar que cualquier gráfico tiene un separador con un tamaño que no excede el ancho de su árbol .

Si el grafo G no es plano, pero se puede incrustar en una superficie de género g , entonces tiene un separador con vértices O(( gn ) 1/2 ). Gilbert, Hutchinson y Tarjan [27] demostraron esto utilizando un enfoque cercano al de Lipton y Tarjan [4] . Agrupan los vértices del gráfico por niveles de búsqueda en anchura y encuentran dos niveles cuya eliminación deja como máximo un componente grande que consiste en una pequeña cantidad de niveles. Este componente restante se puede hacer plano eliminando una serie de rutas de búsqueda en anchura proporcionales al género del gráfico, después de lo cual se puede aplicar el método de Lipton-Tarjan al gráfico plano restante. El resultado se obtiene equilibrando cuidadosamente el tamaño de los dos niveles eliminados y el número de niveles entre ellos. Dada la incrustación de un gráfico, su separador se puede encontrar en el tiempo lineal . Los gráficos del género g tienen separadores de tamaño O(( g Δ n ) 1/2 ) [28] .

Los grafos de género acotado forman un ejemplo de una familia de grafos cerrados bajo la operación de tomar menores , y los teoremas de partición se aplican a familias arbitrarias de grafos cerrados tomando un menor. En particular, si una familia de grafos tiene un menor prohibido con h vértices, entonces tiene un separador con O( h √ n ) vértices, y tal separador se puede encontrar en el tiempo O( n 1 + ε ) para cualquier ε > 0 [29]

El método de los ciclos separadores de Miller, Teng, Thurston y Vavasis [10] se generaliza para las gráficas de intersección de cualquier sistema de bolas d -dimensionales, que tienen la propiedad de que cualquier punto de la superficie está cubierto por bolas como máximo alguna constante número k veces, para gráficos k - vecinos más cercanos en el espacio de dimensión d [10] , y para gráficos que surgen en cuadrículas de elementos finitos [30] . Los separadores esféricos construidos de esta manera dividen el gráfico de entrada en subgráficos con un máximo de n ( d + 1)/( d + 2) vértices. El tamaño de los separadores para gráficos de bolas superpuestas de k veces y gráficos de k vecinos más cercanos es O( k 1/ d n 1 − 1/ d ) [10] .

Aplicaciones

Algoritmos divide y vencerás

Las particiones separadoras se pueden usar para construir algoritmos eficientes de " Divide y vencerás" para resolver problemas en gráficos planos. Un ejemplo de un problema que se puede resolver con este enfoque es encontrar el ciclo más corto en un gráfico dirigido plano ponderado. Puedes hacerlo así:

El tiempo de dos llamadas recursivas para A y B en este algoritmo está dominado por el tiempo de ejecución O(√ n ) del algoritmo de Dijkstra, por lo que este algoritmo encuentra el ciclo más corto en el tiempo O( n 3/2  log  n ).

Wolf-Nielsen [31] proporcionó un algoritmo más rápido para el mismo problema de encontrar el ciclo más corto, que se ejecuta en el tiempo O ( n  log 3 n ) . Su algoritmo usa la misma estructura de divide y vencerás basada en separadores, pero usa separadores de ciclo simple en lugar de separadores arbitrarios, de modo que los vértices del conjunto S pertenecen a la misma cara (para el gráfico interno y para el gráfico externo con respecto a al separador). Luego reemplaza las llamadas individuales O(√ n ) al algoritmo de Dijkstra con algoritmos más sofisticados para encontrar las rutas más cortas desde todos los vértices en una sola cara de un gráfico plano y combinar distancias de dos subgráficos. Para gráficos planos ponderados pero no dirigidos, el ciclo más corto es equivalente al corte más pequeño en el gráfico dual y se puede encontrar en el tiempo O( n  log log  n ) [32] , y el ciclo más corto en un gráfico plano no dirigido de ciclo ponderado (su circunferencia ) se puede encontrar en el tiempo O( n ) [33] . (Sin embargo, el algoritmo más rápido para gráficos no ponderados no se basa en el teorema de partición).

Frederickson propuso en 1986 otro algoritmo rápido para el camino más corto desde una sola fuente mediante el uso del teorema de partición para grafos planos [34] . El algoritmo es una mejora de la búsqueda iterativa de Dijkstra en un subconjunto de vértices cuidadosamente elegido. Esta versión se ejecuta en tiempo O( n √(log n )) en un gráfico con n vértices. Los separadores se utilizan para encontrar la división de un gráfico, es decir, su partición en dos o más subconjuntos, llamados áreas. Se dice que un nodo está contenido en una región si algún borde de la región incide sobre el nodo. Un nodo que está contenido en más de un área se denomina nodo límite de las áreas que lo contienen. El método utiliza la noción de una división en r de un gráfico con n nodos, lo que corresponde a dividir el gráfico en O( n / r ) regiones, cada una de las cuales contiene O( r ) nodos, incluidos O(√ r ) nodos límite . Frederickson demostró que la división r se puede encontrar en el tiempo O( n log n ) aplicando recursivamente el teorema de la partición.

Esquema del algoritmo para resolver el problema.

1. Preparación preliminar . Dividimos el gráfico en subconjuntos de vértices cuidadosamente seleccionados y encontramos los caminos más cortos entre todos los pares de vértices en estos subconjuntos, en los que los vértices intermedios del camino no pertenecen al subconjunto. En esta fase, es necesario transformar el grafo plano G 0   en G , que no tiene vértices con grado mayor a 3. De la fórmula de Euler , el número de vértices en el grafo resultante será n ≤ 6 n 0  −12, donde n 0   es el número de vértices en el gráfico G 0  . Esta fase también proporciona las siguientes propiedades de divisiones r adecuadas. Una división en r apropiada de un gráfico plano es una división en r tal que

2. Buscar

Henzinger et al ampliaron la técnica de división r de Frederickson para el algoritmo para encontrar el camino más corto desde una sola fuente en gráficos planos con longitudes de borde no negativas y propusieron un algoritmo de tiempo lineal [35] . Su método generaliza la noción de una partición de Fredrekson para un gráfico, de modo que ahora una partición ( r , s ) de un gráfico con n nodos se convierte en una partición en regiones O( n / r ), cada una de las cuales contiene r {O(1) }   nodos y como máximo s nodos límite. Si la partición ( r , s ) se repite secuencialmente para particionar en regiones más pequeñas, esto se denomina partición recursiva. El algoritmo utiliza aproximadamente log* n niveles de división. La división recursiva está representada por un árbol con raíz cuyas hojas están etiquetadas con diferentes aristas del gráfico G. La raíz del árbol representa la región que consta de todo el gráfico G , los hijos de la raíz representan las subregiones en las que se divide la región. Cada hoja representa exactamente un borde.

La disección anidada  es una variación basada en separadores del enfoque divide y vencerás del método de eliminación gaussiana para resolver sistemas simétricos dispersos de ecuaciones algebraicas lineales con una estructura gráfica plana, como las que surgen en el método de elementos finitos . El método utiliza la búsqueda de un separador para el gráfico de descripción de la ecuación, excluyendo recursivamente variables en dos subtareas separadas entre sí por un separador y luego excluyendo las variables en el separador [36] . La ocupación de este método (el número de coeficientes distintos de cero de la expansión de Cholesky resultante para una matriz) es O( n  log  n ) [37] [38] , lo que permite que este método compita con métodos iterativos para los mismos problemas [ 36] .

Klein, Moses y Weimann [39] propusieron un algoritmo de memoria lineal O( n log 2  n ) para encontrar las distancias más cortas desde s para todos los nodos de un gráfico plano dirigido con longitudes de arco positivas y negativas que no contiene ciclos negativos. Su algoritmo utiliza separadores de gráficos planos para encontrar una curva de Jordan C que pasa por O(√ n ) nodos (pero no por arcos) de modo que entre n /3 y 2 n /3 nodos estén dentro (el área delimitada por la curva cerrada). c _ Los nodos por los que pasa la curva C son nodos límite . El gráfico original G se divide en dos subgráficos G 0   y G 1 , cortando la incrustación plana a lo largo de la curva C y duplicando los nodos de los límites. Para i =0 y 1, en G i   los nodos límite se encuentran en una cara de F i  .

A continuación se ofrece una descripción general de este enfoque.

Una parte importante de este algoritmo es el uso de funciones de precio y longitud reducida. Para un grafo dirigido G con longitudes de arco ι(•), la función de costo es la función φ de los nodos del grafo G a los números reales . Para un arco uv , la longitud reducida con respecto a φ es ιφ( uv )=ι( uv ) + φ( u ) − φ( v ). Una función de costo admisible es una función que da longitudes reducidas no negativas en todos los arcos de G. Es útil convertir un problema de ruta más corta que tiene longitudes de arco tanto positivas como negativas en un problema con longitudes no negativas, lo que permite utilizar el algoritmo de Dijkstra.

El paradigma divide y vencerás basado en separadores también se utiliza para desarrollar estructuras de datos para algoritmos de gráficos dinámicos [40] [41] y localización de puntos [42] , algoritmos de triangulación de polígonos [22] , caminos más cortos [ 43] [44] , para construir gráficos de vecinos más cercanos [45] y algoritmos de aproximación para encontrar el conjunto independiente máximo en gráficos planos [42] .

Solución exacta de problemas de optimización NP-hard

Cuando se usa programación dinámica en descomposición de árbol o descomposición de rama para un gráfico plano, muchas clases de problemas de optimización NP-hard pueden resolverse exponencialmente en el tiempo dependiendo de √ n o √ n  log  n . Por ejemplo, se conocen límites de este tipo para buscar conjuntos máximos independientes , árboles de Steiner , ciclos hamiltonianos y para resolver el problema del viajante de comercio en gráficos planos [46] . Se pueden usar métodos similares que usan teoremas de partición para gráficos geométricos para resolver el problema del viajante de comercio euclidiano y construir un árbol de Steiner dentro de los mismos límites de tiempo [47] .

Para problemas parametrizados que permiten una reducción paramétrica que conserva la planaridad y reduce el archivo de entrada a un núcleo con un tamaño que depende linealmente del parámetro, este enfoque se puede usar para construir algoritmos fijos paramétricamente solucionables cuyo tiempo de ejecución depende polinómicamente sobre el tamaño del gráfico de entrada y exponencialmente en √ k , donde k  es un parámetro del algoritmo. Por ejemplo, se conocen límites de tiempo de ejecución de este tipo para encontrar cubiertas de vértices y conjuntos dominantes de tamaño k [48] [49] .

Algoritmos de aproximación

Lipton y Tarjan [42] observaron que el teorema de partición se puede utilizar para derivar esquemas de aproximación de tiempo polinomial para problemas de optimización NP-hard en gráficos planos, como encontrar el conjunto independiente máximo . En particular, al truncar la jerarquía de separadores en un lugar adecuado, se puede encontrar un separador de tamaño O( n /√log  n ), cuya eliminación divide el gráfico en subgráficos de tamaño c  log  n para cualquier constante c . Por el teorema de los cuatro colores , hay un conjunto independiente de tamaño al menos n /4, por lo que los nodos eliminados forman una pequeña fracción del conjunto independiente máximo, y los conjuntos independientes máximos en los subgrafos restantes se pueden encontrar de forma independiente en el tiempo exponencialmente dependiente sobre su tamaño. Combinando este enfoque con los métodos de tiempo lineal para construir una jerarquía de separadores [22] con una tabla de búsqueda para reducir el tiempo de búsqueda de conjuntos independientes en subgrafos isomorfos , se pueden construir conjuntos independientes que se desvían de los óptimos por un factor de 1 − O(1/√log  n ) en tiempo lineal. Sin embargo, para una eficiencia garantizada incluso más cercana a 1 que este factor, el enfoque posterior de Baker ( Baker 1994 ) (basado en la descomposición del árbol en lugar de separadores planos) proporciona un mejor compromiso entre el tiempo y la calidad de la aproximación.

Se utilizan esquemas de aproximación similares basados ​​en la construcción de separadores para aproximar otros problemas difíciles, como el problema de cobertura de vértices [50] [51] . Arora, Grigni, Karger, Klein y Voloshin [52] usaron separadores de una manera diferente para aproximar el problema del viajante de comercio para la métrica del camino más corto en gráficos planares ponderados. Su algoritmo utiliza programación dinámica para encontrar el camino más corto que, en cada nivel de la jerarquía del separador, cruza el separador un número limitado de veces. Demostraron que a medida que aumenta el límite del número de intersecciones, las rutas construidas de esta manera tienen una longitud que se aproxima a la ruta óptima.

Compresión de gráficos

Los separadores se utilizan como parte de los algoritmos de compresión de datos para representar gráficos planos y otros gráficos separables utilizando una pequeña cantidad de bits. El principio fundamental de estos algoritmos es elegir un número k y repartir el gráfico plano dado usando separadores en O( n / k ) subgráficos de tamaño como máximo k , con O( n /√ k ) vértices en los separadores. Con una elección adecuada de k (máximo proporcional al logaritmo de n ), el número de subgrafos planos no isomorfos con k vértices es sustancialmente menor que el número de subgrafos en la descomposición, por lo que los gráficos pueden comprimirse construyendo una tabla de todos los posibles subgrafos no isomorfos y representando cada subgrafo en la descomposición por un índice en la tabla. El resto del grafo formado por los vértices del separador se puede representar de forma explícita o con una versión recursiva de la misma estructura de datos. Con este método, se pueden codificar gráficos planos y familias más limitadas de gráficos planos utilizando el número óptimo de bits (en términos de teoría de la información ): si hay gráficos P n con n vértices en una familia de gráficos, entonces un gráfico individual del la familia se puede representar usando solo (1 + o( n ))log 2 P n bits [53] . También se pueden construir vistas de este tipo, en las que se puede comprobar la adyacencia de los vértices, determinar el grado de un vértice y enumerar los vecinos de vértice en tiempo constante (por consulta), ampliando la tabla de subgrafos con información adicional con datos correspondientes a consultas [54] [55] .

Gráficos universales

Un gráfico universal para una familia de gráficos F  es un gráfico que contiene cualquier elemento de la familia F como subgrafo. Los separadores se pueden usar para mostrar que los gráficos planos de n vértices tienen un gráfico universal con n vértices y O( n 3/2 ) aristas [56] .

La construcción utiliza una forma más fuerte del teorema de la partición, en el que el tamaño de los tres subconjuntos de vértices en la partición no depende de la estructura del gráfico: hay un número c , cuyo valor es un factor constante mayor que √ n , tal que los vértices de cualquier gráfico plano con n vértices se pueden dividir en subconjuntos A , S y B sin bordes de A a B y con dimensiones | S | =  c , | un | = | segundo | = ( norte  −  c )/2. Esto se puede demostrar aplicando la forma habitual del teorema de partición repetidamente a las particiones resultantes del gráfico hasta que todos los componentes de la partición se agrupan en dos subconjuntos, cada uno de los cuales tiene menos de n /2 vértices de tamaño, y luego transfiriendo el vértices de estos subconjuntos al separador hasta que no tenga el tamaño dado.

Ahora, este teorema se puede usar para obtener una jerarquía de separadores para un gráfico plano con n vértices, que nuevamente es independiente de la estructura del gráfico: la descomposición del árbol obtenida de esta jerarquía tiene un ancho de O (√ n ) y se puede usar para cualquier gráfico plano. El conjunto de todos los pares de vértices en esta descomposición en árbol, en la que cada uno de los dos vértices pertenece a un nodo común de la descomposición en árbol, forma un grafo trivialmente perfecto con O( n 3/2 ) vértices, que contiene cualquier grafo plano con n vértices como un subgrafo. Una construcción similar muestra que los gráficos planos de grado acotado tienen gráficos universales con aristas O( n  log  n ), donde la constante oculta en la notación O depende del grado del gráfico. Cualquier gráfico universal para gráficos planares (o incluso para árboles de grado no acotado) debe tener aristas Ω( n  log  n ), pero se desconoce si este límite inferior o el límite superior O( n 3/2 ) es nítido para gráficos universales de gráficos planos arbitrarios [56] .

Véase también

Notas

  1. ↑ 1 2 Alon, Seymour, Thomas, 1990 .
  2. ↑ 1 2 3 Djijev, 1982 .
  3. ↑ Jorge, 1973 . En lugar de usar filas y columnas como separador para dividir el gráfico, George usa su unión y divide el gráfico en cuatro partes.
  4. ↑ 1 2 3 4 Lipton, Tarjan, 1979 .
  5. ↑ Holzer, Schulz, Wagner, Prasinos, Zaroliagis, 2009 .
  6. ↑ 12 Miller , 1986 .
  7. ↑ 1 2 Alon, Seymour, Thomas, 1994 .
  8. ↑ Djidjev, Venkatesan, 1997 .
  9. ↑ 1 2 3 Gazit, Miller, 1990 .
  10. ↑ 1 2 3 4 5 6 7 Miller, Teng, Thurston, Vavasis, 1997 .
  11. ↑ Pach, Agarwal, 1995 .
  12. ↑ Eppstein, Miller, Teng, 1995 .
  13. ↑ Spielman, Teng (1996 ).
  14. ↑ Spielman, Teng, 1996 .
  15. ↑ Gremban, Miller, Teng, 1997 .
  16. ↑ Har-Peled, 2011 .
  17. ↑ Donath, Hoffman, 1972 .
  18. ↑ Fiedler, 1973 .
  19. ↑ Spielman, Teng, 2007 .
  20. ↑ Miller ( Miller 1986 ) probó este resultado para grafos planos conectados en 2, mientras que Diks, Djidjev, Sýkora, Vrt'o (1993 ) extendieron el resultado a todos los grafos planos.
  21. ↑ Papadimitriou, Sideri, 1996 .
  22. ↑ 1 2 3 Goodrich, 1995 .
  23. ↑ Seymour, Thomas, 1994 .
  24. ↑ Fomin, Thilikos, 2006a .
  25. ↑ Erdös, Graham, Szemerédi, 1976 .
  26. ↑ Jordania, 1869 .
  27. ↑ Gilbert, Hutchinson, Tarjan, 1984 .
  28. ↑ Sykora, Vrt'o, 1993 .
  29. ↑ Kawarabayashi, Reed, 2010 . Trabajos anteriores sobre separadores de familias cerradas menores - Alon, Seymour, Thomas, 1990 ; Plotkin, Rao, Smith, 1994 ; Caña, Madera, 2009 .
  30. ↑ Miller, Teng, Thurston, Vavasis, 1998 .
  31. ↑ Wulff-Nilsen, 2009 .
  32. ↑ Łącki, Sankowski, 2011 .
  33. ↑ Chang, Lu, 2011 .
  34. ↑ Frederickson, 1987 , pág. 1004-1022.
  35. ↑ Henzinger, Klein, Rao, Subramanian, 1997 .
  36. ↑ 12 Jorge, 1973 .
  37. ↑ Lipton, Rose, Tarjan, 1979 .
  38. ↑ Gilbert, Tarjan, 1986 .
  39. ↑ Klein, Mozes, Weimann, 2009 .
  40. ↑ Eppstein, Galil, Italiano, Spencer, 1996 .
  41. ↑ Eppstein, Galil, Italiano, Spencer, 1998 .
  42. ↑ 1 2 3 Lipton, Tarjan, 1980 .
  43. ↑ Klein, Rao, Rauch, Subramanian, 1994 .
  44. ↑ Tazari, Müller-Hannemann, 2009 .
  45. ↑ Friso, Miller, Teng, 1992 .
  46. ↑ Berna, 1990 ; Deĭneko, Klinz, Woeginger, 2006 ; Dorn, Penninkx, Bodlaender, Fomin, 2005 ; Lipton, Tarjan, 1980 .
  47. ↑ Smith, Wormald, 1998 .
  48. ↑ Alber, Fernau, Niedermeier, 2003 .
  49. ↑ Fomin, Thilikos, 2006b .
  50. ↑ Bar-Yehuda, Even, 1982 .
  51. ↑ Chiba, Nishizeki, Saito, 1981 .
  52. ↑ Arora, Grigni, Karger, Klein, Woloszyn, 1998 .
  53. ↑ Él, Kao, Lu, 2000 .
  54. ↑ Blandford, Blelloch, Kash, 2003 .
  55. ↑ Blelloch, Farzán, 2010 .
  56. ↑ 1 2 Babai, Chung, Erdős, Graham, Spencer, 1982 ; Bhatt, Chung, Leighton, Rosenberg, 1989 ; Chung, 1990 .

Literatura