How to approach Dynamic graph related problems

I asked this question at generic stackoverflow and I was directed here.

It will be great if some one can explain how to approach partial or fully dynamic graph problems in general.

For example:

• Find Shortest Path between two vertices $(u,v)$ in a undirected weighted graph for $n$ instances, when an edge is removed at each instance.

• Find number of connected components in an undirected graph for n instances when an edge is remove at each instance, etc.

I recently encountered this genre of problems in a programming contest. I searched through the web and I found lot of research papers concerning with dynamic graphs [1,2]. I read couple of them and and I couldnt find anything straight forward (clustering, sparsification etc). Sorry for being vague.

I really appreciate if some can provide pointers to understand these concepts better.

• Dynamic Graph Algorithms by D. Eppstein , Z. Galil , G. F. Italiano (1999)

• Shortest paths on dynamic graphs by G. Nannicini, L. Liberti (2008)

It's hard to give you concrete techniques because "dynamic" could mean a wide variety of things, and the algorithms/results depend on your model. Below is an overview of the concerns. Here is a paper that gives an overview of some different concerns and models (related to what Peter cited in another answer).

For dynamic problems in general, the key issues are:

• do you want an exact solution in all cases, or is approximation allowed?

• do you know anything about what changes will occur (e.g. a probability distribution), or are they all equally likely?

• how does the algorithm learn about the changes?

A typical dynamic model is something like the following:

-
Given a graph, you want to compute some property. You are allowed to compute a solution for the initial graph.

-
You are then told one modification: edge $(e,f)$ is deleted. Compute the property on the new graph using limited resources.

-
Repeat 2 for $n$ times.

And here are 3 possible modifications:

-
You aren't allowed to compute the complete solution at the beginning because of information / time / space limitations (one example of which is online algorithms)

-
In step 2, the algorithm is not "told" the modification, but has to find the modification in the graph by querying a data structure or something.

-
A distributed model (like Peter discusses in another answer), where the information is discovered locally and the computation/changes are made locally.

Dynamic models are typically interesting because of resource (e.g. time/space) limitations. In step 2, if I was allowed to compute a complete answer (like I did in step 1) then the problem is easy, since it's just a repeated static graph problem. We're more interested in the smallest amount of resources necessary to compute the change.

StackExchange Computer Science Q#1521, answer score: 12