¿Tienen las familias de grafos cerrados menores? incrustaciones con distorsión limitada?
En informática teórica y geometría métrica , la conjetura de GNRS conecta la teoría de grafos menores , el factor de estiramiento de las incrustaciones y la relación de aproximación de problemas de flujo de múltiples productos básicos . Lleva el nombre de Anupam Gupta, Ilan Newman, Yuri Rabinovich y Alistair Sinclair , quienes lo formularon en 2004. [1]
Formulación
Una formulación de la conjetura implica incrustaciones de las distancias de trayectoria más cortas de gráficos no dirigidos ponderados enespacios , espacios vectoriales reales en los que la distancia entre dos vectores es la suma de sus diferencias de coordenadas. Si una incrustación mapea todos los pares de vértices con distancia a pares de vectores con distancia en el rango entonces su factor de estiramiento o distorsión es la relación; una isometría tiene un factor de estiramiento uno y todas las demás incrustaciones tienen un factor de estiramiento mayor. [1]
Los gráficos que tienen una incrustación con como máximo una distorsión dada se cierran bajo operaciones menores de gráfico , operaciones que eliminan vértices o bordes de un gráfico o contraen algunos de sus bordes. La conjetura de GNRS establece que, a la inversa, toda familia de grafos cerrados menores no triviales se puede incrustar en unespacio con distorsión limitada. Es decir, la distorsión de los gráficos en la familia está limitada por una constante que depende de la familia pero no de los gráficos individuales. Por ejemplo, los gráficos planos se cierran en menores. Por lo tanto, de la conjetura de GNRS se seguiría que los gráficos planos tienen distorsión acotada. [1]
Una formulación alternativa implica análogos del teorema de flujo máximo y corte mínimo para problemas de flujo no dirigido de múltiples productos básicos . La relación entre el flujo máximo y el corte mínimo, en tales problemas, se conoce como brecha de corte de flujo . La brecha de corte de flujo más grande que puede tener un problema de flujo en un gráfico dado es igual a la distorsión del valor óptimo.incrustación del gráfico. [2] [3] Por lo tanto, la conjetura de GNRS puede reformularse diciendo que las familias de gráficas cerradas menores tienen una brecha de corte de flujo acotada. [1]
Resultados relacionados
Arbitrario -Gráficos de vértice (de hecho, arbitrarios -puntos espacios métricos ) tienen incrustaciones con distorsión . [4] Algunos gráficos tienen una brecha de corte de flujo logarítmico y, en particular, esto es cierto para un flujo de múltiples productos básicos en el que cada par de vértices tiene la misma demanda en un gráfico expansor de grado acotado . [5] Por lo tanto, este límite logarítmico en la distorsión de gráficos arbitrarios es estrecho. Los gráficos planos se pueden incrustar con una distorsión más pequeña,. [6]
Aunque la conjetura de GNRS sigue sin resolverse, se ha demostrado para algunas familias de gráficos cerrados menores que existen incrustaciones de distorsión limitada. Estos incluyen las gráficas en serie-paralelo y las gráficas de rango de circuito acotado , [1] las gráficas de ancho de ruta acotado , [7] las 2-clique-sumas de gráficas de tamaño acotado, [8] y el-Gráficos orugalanar . [9]
En contraste con el comportamiento de las incrustaciones métricas en espacios, cada espacio métrico finito tiene incrustaciones en con estiramiento arbitrariamente cercano a uno por el lema de Johnson-Lindenstrauss , y enespacios con estiramiento exactamente uno por la construcción de tramo estrecho .
Ver también
- Cubo parcial , una clase de gráficos sin ponderación sin distorsión-Embeddings
Referencias
- ^ a b c d e Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair (2004), "Cortes, árboles y-embeddings of graphs ", Combinatorica , 24 (2): 233–269, doi : 10.1007 / s00493-004-0015-x , MR 2071334
- ^ Avis, David ; Deza, Michel (1991), "El cono cortado,capacidad de integración , complejidad y flujos de productos múltiples ", Networks , 21 (6): 595–617, doi : 10.1002 / net.3230210602 , MR 1128272
- ^ Linial, Nathan ; Londres, Eran; Rabinovich, Yuri (1995), "La geometría de los gráficos y algunas de sus aplicaciones algorítmicas", Combinatorica , 15 (2): 215–245, doi : 10.1007 / BF01200757 , MR 1337355
- ^ Bourgain, J. (1985), "Sobre la incorporación de Lipschitz de espacios métricos finitos en el espacio de Hilbert", Israel Journal of Mathematics , 52 (1–2): 46–52, doi : 10.1007 / BF02776078 , MR 0815600
- ^ Leighton, Tom ; Rao, Satish (1999), "Teoremas de corte mínimo de flujo máximo de productos múltiples y su uso en el diseño de algoritmos de aproximación", Journal of the ACM , 46 (6): 787–832, doi : 10.1145 / 331524.331526 , MR 1753034
- ^ Rao, Satish (1999), "Pequeñas distorsiones y volúmenes que preservan las incrustaciones para métricas planas y euclidianas", Actas del Decimoquinto Simposio Anual sobre Geometría Computacional (SoCG '99) , Nueva York: ACM, págs. 300-306, doi : 10.1145 /304893.304983 , MR 1802217
- ^ Lee, James R .; Sidiropoulos, Anastasios (2013), "Pathwidth, trees, and random embeddings", Combinatorica , 33 (3): 349–374, arXiv : 0910.1409 , doi : 10.1007 / s00493-013-2685-8 , MR 3144806
- ^ Lee, James R .; Poore, Daniel E. (2013), "Sobre la conjetura de incrustación de 2 sumas", Actas del Vigésimo Noveno Simposio Anual sobre Geometría Computacional (SoCG '13) , Nueva York: ACM, págs. 197–206, doi : 10.1145 /2462356.2492436 , Señor 3208212
- ^ Chekuri, Chandra; Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair (2006), "Embedding-Gráficos planos en ", SIAM Journal on Discrete Mathematics , 20 (1): 119-136, doi : 10.1137 / S0895480102417379 , MR 2257250