En el estudio de algoritmos de gráficos , una representación gráfica implícita (o más simplemente un gráfico implícito ) es un gráfico cuyos vértices o aristas no se representan como objetos explícitos en la memoria de una computadora, sino que se determinan algorítmicamente a partir de una entrada más concisa.
Representaciones de barrio
La noción de gráfico implícito es común en varios algoritmos de búsqueda que se describen en términos de gráficos. En este contexto, un gráfico implícito puede definirse como un conjunto de reglas para definir todos los vecinos de cualquier vértice especificado. [1] Este tipo de representación gráfica implícita es análoga a una lista de adyacencia , ya que proporciona un fácil acceso a los vecinos de cada vértice. Por ejemplo, al buscar una solución a un rompecabezas como el Cubo de Rubik , se puede definir un gráfico implícito en el que cada vértice representa uno de los posibles estados del cubo y cada borde representa un movimiento de un estado a otro. Es sencillo generar los vecinos de cualquier vértice probando todos los movimientos posibles en el rompecabezas y determinando los estados alcanzados por cada uno de estos movimientos; sin embargo, es necesaria una representación implícita, ya que el espacio de estado del cubo de Rubik es demasiado grande para permitir que un algoritmo enumere todos sus estados. [2]
En la teoría de la complejidad computacional , se han definido varias clases de complejidad en relación con los gráficos implícitos, definidos como anteriormente por una regla o algoritmo para enumerar los vecinos de un vértice. Por ejemplo, PPA es la clase de problemas en los que se da como entrada un gráfico implícito no dirigido (en el que los vértices son cadenas binarias de n bits, con un algoritmo de tiempo polinomial para enumerar los vecinos de cualquier vértice) y un vértice de grado impar. en la gráfica, y debe encontrar un segundo vértice de grado impar. Según el lema del apretón de manos , tal vértice existe; encontrar uno es un problema en NP , pero los problemas que se pueden definir de esta manera pueden no ser necesariamente NP-completos , ya que se desconoce si PPA = NP. PPAD es una clase análoga definida en gráficos dirigidos implícitos que ha atraído la atención en la teoría de juegos algorítmica porque contiene el problema de calcular un equilibrio de Nash . [3] El problema de probar la accesibilidad de un vértice a otro en un grafo implícito también se puede utilizar para caracterizar clases de complejidad no determinista limitadas por el espacio, incluida NL (la clase de problemas que puede caracterizarse por la accesibilidad en grafos dirigidos implícitos cuyos vértices son O (log n ) cadenas de bits de bits), SL (la clase análoga para gráficos no dirigidos) y PSPACE (la clase de problemas que pueden caracterizarse por la accesibilidad en gráficos implícitos con cadenas de bits de longitud polinomial). En este contexto de teoría de la complejidad, los vértices de un gráfico implícito pueden representar los estados de una máquina de Turing no determinista , y los bordes pueden representar posibles transiciones de estado, pero los gráficos implícitos también pueden usarse para representar muchos otros tipos de estructura combinatoria. [4] PLS , otra clase de complejidad, captura la complejidad de encontrar óptimos locales en un gráfico implícito. [5]
Los modelos de gráficos implícitos también se han utilizado como una forma de relativización para probar separaciones entre clases de complejidad que son más fuertes que las separaciones conocidas para modelos no relativizados. Por ejemplo, Childs et al. utilizó representaciones de vecindad de gráficos implícitos para definir un problema de recorrido de gráfico que se puede resolver en tiempo polinomial en una computadora cuántica, pero que requiere un tiempo exponencial para resolverlo en cualquier computadora clásica. [6]
Esquemas de etiquetado de adyacencia
En el contexto de representaciones eficientes de grafos, JH Muller definió una estructura local o esquema de etiquetado de adyacencia para un grafo G en una familia F dada de grafos para ser una asignación de un identificador de O (log n ) bits a cada vértice de G , junto con un algoritmo (que puede depender de F , pero es independiente de la gráfica individuo G ) que toma como entrada dos identificadores de vértices y determina si son o no los puntos finales de una ventaja en G . Es decir, este tipo de representación implícita es análoga a una matriz de adyacencia : es sencillo verificar si dos vértices son adyacentes, pero encontrar los vecinos de cualquier vértice puede implicar recorrer todos los vértices y probar cuáles son vecinos. [7]
Las familias de gráficos con esquemas de etiquetado de adyacencia incluyen:
- Gráficos de grados acotados
- Si cada vértice en G tiene como máximo d vecinos, se pueden numerar los vértices de G de 1 an y dejar que el identificador de un vértice sea la tupla ( d + 1) de su propio número y los números de sus vecinos. Dos vértices son adyacentes cuando los primeros números de sus identificadores aparecen más adelante en el identificador del otro vértice. De manera más general, se puede utilizar el mismo enfoque para proporcionar una representación implícita de gráficos con arboricidad limitada o degeneración limitada , incluidos los gráficos planos y los gráficos de cualquier familia de gráficos cerrados menores . [8] [9]
- Gráficos de intersección
- Un gráfico de intervalo es el gráfico de intersección de un conjunto de segmentos de línea en la línea real . Se le puede dar un esquema de etiquetado de adyacencia en el que los puntos que son puntos finales de segmentos de línea se numeran de 1 a 2 ny cada vértice del gráfico está representado por los números de los dos puntos finales de su intervalo correspondiente. Con esta representación, se puede comprobar si dos vértices son adyacentes comparando los números que los representan y verificando que estos números definen intervalos superpuestos. El mismo enfoque funciona para otros gráficos de intersección geométrica, incluidos los gráficos de boxicidad acotada y los gráficos circulares , y las subfamilias de estas familias, como los gráficos hereditarios de distancia y las cografías . [8] [10] Sin embargo, una representación gráfica de intersección geométrica no siempre implica la existencia de un esquema de etiquetado de adyacencia, porque puede requerir más de un número logarítmico de bits para especificar cada objeto geométrico. Por ejemplo, representar un gráfico como un gráfico de disco unitario puede requerir exponencialmente muchos bits para las coordenadas de los centros del disco. [11]
- Gráficos de comparabilidad de baja dimensión
- El gráfico de comparabilidad para un conjunto parcialmente ordenado tiene un vértice para cada elemento del conjunto y un borde entre dos elementos del conjunto que están relacionados por el orden parcial. La dimensión de orden de una orden parcial es el número mínimo de órdenes lineales cuya intersección es la orden parcial dada. Si un orden parcial tiene una dimensión de orden acotada, entonces se puede definir un esquema de etiquetado de adyacencia para los vértices en su gráfico de comparabilidad etiquetando cada vértice con su posición en cada uno de los órdenes lineales definitorios y determinando que dos vértices son adyacentes si cada par correspondiente de números en sus etiquetas tiene la misma relación de orden que cada par. En particular, esto permite un esquema de etiquetado de adyacencia para los gráficos de comparabilidad cordal , que provienen de órdenes parciales de dimensión como máximo cuatro. [12] [13]
La conjetura del grafo implícito
¿Todas las familias de gráficos hereditarios de crecimiento lento tienen una representación implícita?
No todas las familias de gráficos tienen estructuras locales. Para algunas familias, un simple argumento de conteo prueba que los esquemas de etiquetado de adyacencia no existen: solo se pueden usar O ( n log n ) bits para representar un gráfico completo, por lo que una representación de este tipo solo puede existir cuando el número de n- vértice gráficos en la familia dada F es como máximo 2 O ( n log n ) . Las familias de gráficos que tienen un número mayor de gráficos que este, como los gráficos bipartitos o los gráficos sin triángulos , no tienen esquemas de etiquetado de adyacencia. [8] [10] Sin embargo, incluso las familias de gráficos en las que el número de gráficos en la familia es pequeño pueden no tener un esquema de etiquetado de adyacencia; Por ejemplo, la familia de gráficos con menos aristas que vértices tiene 2 O ( n log n ) n -gráficos de vértices pero no tiene un esquema de etiquetado de adyacencia, porque uno podría transformar cualquier gráfico dado en un gráfico más grande en esta familia agregando un nuevo vértice aislado para cada borde, sin cambiar su etiquetabilidad. [7] [10] Kannan y col. preguntó si tener una caracterización de subgrafo prohibido y tener como máximo 2 O ( n log n ) n -gráficos de vértice son suficientes para garantizar la existencia de un esquema de etiquetado de adyacencia; esta pregunta, que Spinrad reafirmó como una conjetura, permanece abierta. [8] [10] Entre las familias de gráficos que satisfacen las condiciones de la conjetura y para las que no se conoce un esquema de etiquetado de adyacencia se encuentran la familia de gráficos de disco y los gráficos de intersección de segmentos de línea.
Esquemas de etiquetado y gráficos universales inducidos
Si una familia de grafos F tiene un esquema de etiquetado de adyacencia, entonces los grafos n -vertex en F pueden representarse como subgrafos inducidos de un grafo universal inducido común de tamaño polinomial, el gráfico que consta de todos los posibles identificadores de vértice. Por el contrario, si se puede construir un grafo universal inducido de este tipo, entonces las identidades de sus vértices pueden usarse como etiquetas en un esquema de etiquetado de adyacencia. [8] Para esta aplicación de representaciones gráficas implícitas, es importante que las etiquetas utilicen la menor cantidad de bits posible, porque el número de bits en las etiquetas se traduce directamente en el número de vértices en el gráfico universal inducido. Alstrup y Rauhe demostraron que cualquier árbol tiene un esquema de etiquetado de adyacencia con log 2 n + O ( log * n ) bits por etiqueta, de lo cual se deduce que cualquier gráfico con arboricidad k tiene un esquema con k log 2 n + O ( log * n ) bits por etiqueta y un gráfico universal con n k 2 O ( log * n ) vértices. En particular, los gráficos planos tienen arboricidad como máximo tres, por lo que tienen gráficos universales con un número casi cúbico de vértices. [14] Este límite fue mejorado por Gavoille y Labourel, quienes demostraron que los gráficos planos y las familias de gráficos cerrados menores tienen un esquema de etiquetado con 2 log 2 n + O (log log n ) bits por etiqueta, y que los gráficos de ancho de árbol acotado tienen un esquema de etiquetado con log 2 n + O (log log n ) bits por etiqueta. [15] Bonamy, Gavoille y Piliczuk mejoraron nuevamente el límite de los gráficos planos, que demostraron que los gráficos planos tienen un esquema de etiquetado con ( 4/3 + o (1)) log 2 n bits por etiqueta. [16] Finalmente, Dujmović et al demostraron que los gráficos planos tienen un esquema de etiquetado con (1 + o (1)) log 2 n bits por etiqueta, lo que da un gráfico universal con n 1 + o (1) vértices. [17]
Evasividad
La conjetura de Aanderaa-Karp-Rosenberg se refiere a gráficos implícitos dados como un conjunto de vértices etiquetados con una regla de caja negra para determinar si dos vértices son adyacentes. Esta definición difiere de un esquema de etiquetado de adyacencia en que la regla puede ser específica para un gráfico en particular en lugar de ser una regla genérica que se aplica a todos los gráficos de una familia. Debido a esta diferencia, cada gráfico tiene una representación implícita. Por ejemplo, la regla podría ser buscar el par de vértices en una matriz de adyacencia separada. Sin embargo, un algoritmo al que se le da como entrada un gráfico implícito de este tipo debe operar sobre él solo a través de la prueba de adyacencia implícita, sin referencia a cómo se implementa la prueba.
Una propiedad de gráfico es la cuestión de si un gráfico pertenece a una familia de gráficos dada; la respuesta debe permanecer invariable bajo cualquier reetiquetado de los vértices. En este contexto, la pregunta que debe determinarse es cuántos pares de vértices deben probarse para determinar la adyacencia, en el peor de los casos, antes de que se pueda determinar que la propiedad de interés es verdadera o falsa para un gráfico implícito dado. Rivest y Vuillemin demostraron que cualquier algoritmo determinista para cualquier propiedad de grafo no trivial debe probar un número cuadrático de pares de vértices. [18] La conjetura completa de Aanderaa-Karp-Rosenberg es que cualquier algoritmo determinista para una propiedad de grafo monótono (uno que permanece verdadero si se agregan más aristas a un grafo con la propiedad) debe en algunos casos probar cada par posible de vértices. Se ha demostrado que varios casos de la conjetura son verdaderos, por ejemplo, se sabe que es cierto para gráficas con un número primo de vértices [19], pero la conjetura completa permanece abierta. También se han estudiado variantes del problema para algoritmos aleatorios y algoritmos cuánticos.
Bender y Ron han demostrado que, en el mismo modelo utilizado para la conjetura de la evasión, es posible en tiempo constante distinguir gráficos acíclicos dirigidos de gráficos que están muy lejos de ser acíclicos. Por el contrario, un tiempo tan rápido no es posible en modelos de gráficos implícitos basados en vecindarios, [20]
Ver también
- Grupo de caja negra , un modelo implícito para algoritmos teóricos de grupos
- Oracle matroid , un modelo implícito para algoritmos matroid
Referencias
- ^ Korf, Richard E. (2008), "Búsqueda gráfica implícita basada en disco en tiempo lineal", Journal of the ACM , 55 (6), artículo 26, 40pp, doi : 10.1145 / 1455248.1455250 , MR 2477486.
- ^ Korf, Richard E. (2008), "Minimizar la E / S de disco en la búsqueda de dos bits primero en amplitud" (PDF) , Proc. 23ª AAAI Conf. sobre inteligencia artificial , págs. 317–324,
El cubo de Rubik estándar de 3 × 3 × 3 contiene 4,3252 × 10 19 estados y es demasiado grande para realizar una búsqueda exhaustiva.
- ^ Papadimitriou, Christos (1994), "Sobre la complejidad del argumento de la paridad y otras pruebas ineficientes de existencia" (PDF) , Journal of Computer and System Sciences , 48 (3): 498–532, doi : 10.1016 / S0022-0000 ( 05) 80063-7 , archivado desde el original (PDF) en 03/04/2016 , recuperado 2011-07-12
- ^ Immerman, Neil (1999), "Ejercicio 3.7 (Todo es un gráfico)" , Complejidad descriptiva , Textos de posgrado en Ciencias de la Computación, Springer-Verlag, p. 48, ISBN 978-0-387-98600-5.
- ^ Yannakakis, Mihalis (2009), "Equilibrios, puntos fijos y clases de complejidad", Computer Science Review , 3 (2): 71–85, arXiv : 0802.2831 , doi : 10.1016 / j.cosrev.2009.03.004.
- ^ Childs, Andrew M .; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003), "Aceleración algorítmica exponencial mediante un paseo cuántico", Actas del trigésimo quinto Simposio Anual de ACM sobre Teoría de la Computación , Nueva York: ACM, págs. 59-68, arXiv : quant-ph / 0209131 , doi : 10.1145 / 780,542.780552 , MR 2121062.
- ^ a b Muller, John Harold (1988), Estructura local en clases de gráficos , Ph.D. tesis, Instituto de Tecnología de Georgia.
- ^ a b c d e Kannan, Sampath; Naor, Moni ; Rudich, Steven (1992), "Representación implícita de gráficos", SIAM Journal on Discrete Mathematics , 5 (4): 596–603, doi : 10.1137 / 0405049 , MR 1186827.
- ^ Chrobak, Marek; Eppstein, David (1991), "Orientaciones planas con bajo grado de salida y compactación de matrices de adyacencia" (PDF) , Informática teórica , 86 (2): 243-266, doi : 10.1016 / 0304-3975 (91) 90020- 3.
- ^ a b c d Spinrad, Jeremy P. (2003), "2. Representación gráfica implícita", Representaciones gráficas eficientes , págs. 17-30, ISBN 0-8218-2815-0.
- ^ Kang, Ross J .; Müller, Tobias (2011), Esfera y representaciones producto escalar de gráficos (PDF) , archivados desde el original (PDF) en 2012-03-16 , recuperado 2011-07-12.
- ^ Ma, Tze Heng; Spinrad, Jeremy P. (1991), "Órdenes parciales sin ciclo y gráficos de comparabilidad de cuerdas", Order , 8 (1): 49–61, doi : 10.1007 / BF00385814 , MR 1129614.
- ^ Curtis, Andrew R .; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010), "Una representación implícita de gráficos de comparabilidad cordal en tiempo lineal", Matemáticas aplicadas discretas , 158 (8): 869–875, doi : 10.1016 / j.dam.2010.01.005 , MR 2602811.
- ^ Alstrup, Stephen; Rauhe, Theis (2002), "Pequeños gráficos universales inducidos y representaciones gráficas implícitas compactas" (PDF) , Actas del 43 ° Simposio anual del IEEE sobre fundamentos de la informática , págs. 53–62, doi : 10.1109 / SFCS.2002.1181882 , archivado desde el original (PDF) el 2011-09-27 , consultado el 2011-07-13.
- ^ Arnaud, Labourel; Gavoille, Cyril (2007), "Representación implícita más corta para gráficos planos y gráficos de ancho de árbol acotado" (PDF) , Actas del 15º Simposio europeo anual sobre algoritmos , págs. 582–593, doi : 10.1007 / 978-3-540-75520 -3_52.
- ^ Bonamy, Marthe; Gavoille, Cyril; Pilipczuk, Michał (2020), "Shorter Labeling Schemes for Planar Graphs", Actas del Simposio 2020 ACM-SIAM sobre algoritmos discretos , págs. 446–462, arXiv : 1908.03341 , doi : 10.1007 / 978-3-540-75520- 3_52.
- ^ Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2020), "Etiquetado de adyacencia para gráficos planos (y más allá)", 61º Simposio anual de IEEE sobre fundamentos de la informática ]], págs. 577–588, arXiv : 2003.04280 , doi : 10.1007 / 978-3-540 -75520-3_52.
- ^ Rivest, Ronald L .; Vuillemin, Jean (1975), "Una generalización y prueba de la conjetura de Aanderaa-Rosenberg", Proc. Séptimo Simposio ACM sobre Teoría de la Computación , Albuquerque, Nuevo México, Estados Unidos, págs. 6–11, doi : 10.1145 / 800116.803747.
- ^ Kahn, Jeff; Saks, Michael ; Sturtevant, Dean (1983), "Un enfoque topológico de la evasividad", Simposio sobre los fundamentos de la informática , Los Alamitos, CA, EE. UU .: IEEE Computer Society, págs. 31–33, doi : 10.1109 / SFCS.1983.4.
- ^ Bender, Michael A .; Ron, Dana (2000), "Prueba de aciclicidad de gráficos dirigidos en tiempo sublineal", Autómatas, lenguajes y programación (Ginebra, 2000) , Lecture Notes in Comput. Sci., 1853 , Berlín: Springer, págs. 809–820, doi : 10.1007 / 3-540-45022-X_68 , MR 1795937.