En la teoría de grafos y la teoría de la complejidad computacional , un grafo de Frankl-Rödl es un grafo definido conectando pares de vértices de un hipercubo que se encuentran a una distancia par especificada entre sí. Los gráficos de este tipo están parametrizados por la dimensión del hipercubo y por la distancia entre vértices adyacentes.
Los gráficos de Frankl – Rödl llevan el nombre de Péter Frankl y Vojtěch Rödl , quienes demostraron en 1987 que (para ciertos rangos de los parámetros del gráfico) tienen un número de independencia pequeño y un número cromático alto . [1] Desde entonces, se han vuelto de interés para los teóricos de la complejidad computacional, como ejemplos difíciles de algoritmos de aproximación basados en programación semidefinida para la cobertura de vértices y problemas de coloración de gráficos . Sus propiedades con respecto a estos algoritmos se han utilizado para cuestionar la conjetura de juegos únicos .
Definición y ejemplos
Sea n un entero positivo y sea γ un número real en el intervalo unitario 0 ≤ γ ≤ 1 . Suponga además que (1 - γ ) n es un número par . Luego, el gráfico de Frankl-Rödles el gráfico en los 2 n vértices de un hipercubo de unidad n- dimensional [0,1] n en el que dos vértices son adyacentes cuando su distancia de Hamming (el número de coordenadas en las que los dos difieren) es exactamente (1 - γ ) n . [2] Aquí, el requisito de que (1 - γ ) n sea par es necesario para evitar que el resultado sea un gráfico bipartito . El gráfico de Frankl-Rödl estará necesariamente desconectado (con al menos un componente conectado para cada uno de los dos lados de la bipartición del gráfico de hipercubo correspondiente ) pero esto no es problemático para sus aplicaciones.
Como ejemplo, el gráfico de Frankl-Rödl conecta vértices separados por dos pasos en un cubo tridimensional ordinario, como se muestra en la ilustración. Geométricamente, este patrón de conexión forma una forma conocida como stella octangula ; grafica-teóricamente, forma dos componentes conectados, cada uno de los cuales es un grafo completo de cuatro vértices . De manera similar, el gráfico de Frankl-Rödlconecta vértices separados por dos pasos en un hipercubo de cuatro dimensiones, y da como resultado un gráfico que consta de dos copias del gráfico de cóctel K 2,2,2,2 . Los dos gráficos de Frankl-Rödl de dimensión cinco, y , están formados cada uno a partir de dos copias de los dos gráficos de Clebsch complementarios de grado cinco y diez, respectivamente.
Propiedades
El gráfico de Frankl-Rödl es una gráfica regular , de grado
Hereda las simetrías de su hipercubo subyacente, lo que lo convierte en un gráfico simétrico .
Como demostraron Frankl y Rödl (1987) , [3] cuando γ ≤ 1/4 , el tamaño de un conjunto independiente máximo en un gráfico de Frankl-Rödl es
El Ω en esta fórmula es una instancia de notación Ω grande . Para valores constantes de γ y variable n , este tamaño de conjunto independiente es una pequeña fracción de los 2 n vértices del gráfico. Más precisamente, esta fracción es inversamente proporcional a una función exponencial de ny una función polinomial del tamaño del gráfico. Debido a que cada color en la coloración adecuada del gráfico de Frankl-Rödl forma un conjunto independiente con pocos vértices, el número de colores debe ser grande (nuevamente, una función polinomial del tamaño del gráfico).
En complejidad computacional
El problema de la cobertura de vértices implica encontrar un conjunto de vértices que toque cada borde del gráfico. Es NP-duro pero se puede aproximar dentro de una relación de aproximación de dos, por ejemplo, tomando los puntos finales de los bordes emparejados en cualquier emparejamiento máximo . La evidencia de que esta es la mejor relación de aproximación posible de un algoritmo de aproximación de tiempo polinomial la proporciona el hecho de que, cuando se representa como un programa semidefinido , el problema tiene una brecha de integralidad de dos; esta brecha es la relación entre el valor de solución de la solución entera (una cobertura de vértice válida) y de su relajación semidefinida . De acuerdo con la conjetura de los juegos únicos , para muchos problemas como este, la relación de aproximación óptima es proporcionada por la brecha de integralidad de su relajación semidefinida. Sin embargo, los gráficos de Frankl-Rödl proporcionan las únicas instancias conocidas de cobertura de vértices para las que la brecha de integralidad puede ser tan mala como dos. [4]
Las gráficas de Frankl – Rödl también se han utilizado para estudiar aproximaciones semidefinidas para colorear gráficas. En esta aplicación, en particular, los investigadores han estudiado la colorabilidad del gráfico 3 en relación con los gráficos de Frankl-Rödl con el parámetro γ = 1/4 . Aunque los gráficos de Frankl-Rödl con este valor de parámetro tienen un número cromático alto, la programación semidefinida es incapaz de distinguirlos de los gráficos de 3 colores. [5] [6] [7] Sin embargo, para estos gráficos, los métodos algebraicos basados en sumas polinomiales de cuadrados pueden proporcionar límites más fuertes que certifiquen su necesidad de muchos colores. Este resultado desafía la optimización de la programación semidefinida y la exactitud de la conjetura de los juegos únicos. [2]
Referencias
- ^ Frankl, Peter ; Rödl, Vojtěch (1987), "Forbidden intersections", Transactions of the American Mathematical Society , 300 (1): 259-286, doi : 10.2307 / 2000598 , JSTOR 2000598 , MR 0871675.
- ^ a b Tan, Li-Yang; Zhou, Yuan; O'Donnell, Ryan; Kauers, Manuel (2016), "Desigualdades hipercontractivas a través de SOS y el gráfico de Frankl-Rödl", Análisis discreto , 2016: 4: 20pp, arXiv : 1212.5324 , doi : 10.19086 / da.612.
- ^ Ver también Georgiou, Konstantinos; Magen, Avner ; Pitassi, Toniann ; Tourlakis, Iannis (2010), "Brechas de integralidad de 2 - o (1) para SDP de cobertura de vértice en la jerarquía de Lovász-Schrijver" (PDF) , SIAM Journal on Computing , 39 (8): 3553–3570, doi : 10.1137 / 080721479 , MR 2745765.
- ^ Georgiou y col. (2010) ; Tan y col. (2016) .
- ^ Karger, David ; Motwani, Rajeev ; Sudán, Madhu (1998), "Coloración aproximada de gráficos mediante programación semidefinida", Journal of the ACM , 45 (2): 246–265, arXiv : cs / 9812008 , doi : 10.1145 / 274787.274791 , MR 1623197.
- ^ Kleinberg, Jon ; Goemans, Michel X. (1998), "La función theta de Lovász y una relajación de programación semidefinida de la cobertura de vértices", SIAM Journal on Discrete Mathematics , 11 (2): 196-204, doi : 10.1137 / S0895480195287541 , MR 1617152.
- ^ Charikar, Moses (2002), "Sobre relajaciones de programación semidefinidas para colorear gráficos y cubrir vértices" , Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos (SODA '02) , Filadelfia, Pensilvania, EE. UU.: Sociedad de Matemáticas Industriales y Aplicadas , págs. 616–620 , ISBN 978-0-89871-513-2.