Cómo abordar problemas relacionados con gráficos dinámicos

Hice esta pregunta en stackoverflow genérico y fui dirigido aquí.

Será genial si alguien puede explicar cómo abordar los problemas de gráficos parciales o totalmente dinámicos en general.

Por ejemplo:

• Encuentre la ruta más corta entre dos vértices en un gráfico ponderado no dirigido para n instancias, cuando se elimina un borde en cada instancia.$(u,v)$$n$
• Encuentre el número de componentes conectados en un gráfico no dirigido para n instancias cuando se elimina un borde en cada instancia, etc.

Recientemente encontré este género de problemas en un concurso de programación. Busqué en la web y encontré muchos trabajos de investigación relacionados con gráficos dinámicos [1,2]. Leí un par de ellos y no pude encontrar nada sencillo (agrupación, dispersión, etc.). Perdón por ser vago.

Realmente aprecio si algunos pueden proporcionar sugerencias para comprender mejor estos conceptos.

1. Algoritmos de gráficos dinámicos de D. Eppstein, Z. Galil, GF Italiano (1999)
2. Caminos más cortos en gráficos dinámicos por G. Nannicini, L. Liberti (2008)

Es difícil darle técnicas concretas porque "dinámico" podría significar una amplia variedad de cosas, y los algoritmos / resultados dependen de su modelo. A continuación se muestra una descripción general de las preocupaciones. Aquí hay un documento que ofrece una visión general de algunas preocupaciones y modelos diferentes (relacionados con lo que Peter citó en otra respuesta).

Para problemas dinámicos en general, los temas clave son:

• ¿Desea una solución exacta en todos los casos, o se permite la aproximación?
• ¿sabe algo acerca de qué cambios ocurrirán (por ejemplo, una distribución de probabilidad), o son todos igualmente probables?
• ¿Cómo se entera el algoritmo de los cambios?

Un modelo dinámico típico es algo como lo siguiente:

1. Dado un gráfico, desea calcular alguna propiedad. Se le permite calcular una solución para el gráfico inicial.

2. Luego se le indica una modificación: el borde se elimina. Calcule la propiedad en el nuevo gráfico utilizando recursos limitados .$(e,f)$

3. Repita 2 por veces.$n$

Y aquí hay 3 posibles modificaciones:

• No puede calcular la solución completa al principio debido a limitaciones de información / tiempo / espacio (un ejemplo de esto son los algoritmos en línea )

• En el paso 2, al algoritmo no se le "dice" la modificación, pero tiene que encontrar la modificación en el gráfico al consultar una estructura de datos o algo así.

• Un modelo distribuido (como Peter analiza en otra respuesta), donde la información se descubre localmente y los cálculos / cambios se realizan localmente.

Los modelos dinámicos suelen ser interesantes debido a las limitaciones de recursos (por ejemplo, tiempo / espacio). En el paso 2, si se me permitió calcular una respuesta completa (como hice en el paso 1), entonces el problema es fácil, ya que es solo un problema de gráfico estático repetido . Estamos más interesados ​​en la menor cantidad de recursos necesarios para calcular el cambio.

Los modelos de gráficos dinámicos se han estudiado intensamente en informática distribuida. Para algoritmos distribuidos, el cálculo se estructura en rondas y la topología de los gráficos (= red) puede sufrir algunos cambios de ronda a ronda, que están bajo el control de un adversario. Además, cada nodo del gráfico ejecuta un algoritmo que puede enviar un mensaje a sus vecinos (¡actuales!). (Este mensaje es la entrada del algoritmo de los vecinos en la siguiente ronda). Lo que hace que las cosas sean interesantes es que un nodo no "ve" todo el gráfico sino solo su vecindario local.

Los problemas que se consideran en esta configuración son, por ejemplo, la difusión de información donde cada nodo en el gráfico inicialmente contiene un token y eventualmente desea que cada nodo haya visto todos los tokens. El objetivo es diseñar algoritmos que logren esto en el menor número de rondas, utilizando el menor número de mensajes. Ver [2] para una encuesta reciente.

Para la configuración no distribuida, es posible que desee ver [1], que es una extensión del documento que ha mencionado.

[1] Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, Fabio Vandin: Algoritmos sobre gráficos en evolución . ITCS 2012: 149-160

[2] Fabian Kuhn, Rotem Oshman: Redes dinámicas: modelos y algoritmos . SIGACT News 42 (1): 82-96 (2011)

Basándome en las respuestas de @Peter (es un comentario muy largo, por lo que acabo de incluir como respuesta que alguien se beneficiará de ello).

Sugeriría la siguiente referencia:

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: gráficos que varían en el tiempo y redes dinámicas. IJPEDS 27 (5): 387-408 (2012)

$\Delta$

Lo realmente importante de esta clasificación es que existen relaciones de inclusión entre las diferentes clases. Entonces, si resuelve un problema en una clase determinada, lo resolverá en cualquier otra clase en la que esté incluido.

Los mismos autores presentaron algoritmos de transmisión en algunos de los gráficos mencionados. Proporcionaron diferentes métricas de rendimiento relacionadas con el tiempo (es decir, una definición diferente del tiempo más corto). En la radiodifusión, la idea es que cada nodo construya una vista de la red en el dominio del tiempo. Esto se hace escuchando repetidamente a los vecinos y enviando información a los vecinos. Si se asume la periodicidad, un nodo puede decir cuál es la ruta de tiempo más corta a otro nodo. Utiliza esta información en el enrutamiento. Más detalles se pueden encontrar en:

Arnaud Casteigts, Paola Flocchini, Bernard Mans, Nicola Santoro: Cálculos deterministas en gráficos que varían en el tiempo: Difusión bajo movilidad no estructurada. IFIP TCS 2010: 111-124

$u$$v$$\{(u,x_1), (x_1, x _2), ...., (x _k, v)\}$$u$$v$$v$$u$

Asistí a una conferencia de los autores anteriores. Según tengo entendido, afirman que estamos lejos de poder manejar algoritmos de gráficos dinámicos (siguiendo las definiciones que siguen). Que todavía estamos en el caso de clases simples. De hecho, afirman que la mayoría de los algoritmos de computación móvil simplemente suponen que sus algoritmos son demasiado rápidos para ejecutarse mientras la red está en transición. (que creo que escuché mucho) - O simplemente, asuma la periodicidad de la apariencia de los bordes (vea redes tolerantes al retraso, etc.)