16
$\begingroup$

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.

  1. Dynamic Graph Algorithms by D. Eppstein , Z. Galil , G. F. Italiano (1999)
  2. Shortest paths on dynamic graphs by G. Nannicini, L. Liberti (2008)
Improve this question
$\endgroup$

3 Answers 3

Reset to default
12
$\begingroup$

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:

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

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

  3. 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks a lot for the reply. I was trying to understand the complexities and ways of a solving a simple partially dynamic graph problem. $\endgroup$
    – Prakash
    Apr 27, 2012 at 16:23
  • $\begingroup$ Thanks a lot for the reply. I will go through the papers. I was trying to understand the complexities and ways of a solving a simple partially dynamic graph problem. For example, Given a set of cities, connected by roads, undirected and weighted by distance. Find the shortest path between 2 cities, on n instances, when a road is blocked at each instance for various reasons. Running Dijkstra for n instance is impractical, is there a way to adapt existing algorithms like A* to solve these problems with better time bound, or approaches discussed in the papers are the only way to go. $\endgroup$
    – Prakash
    Apr 27, 2012 at 16:29
  • $\begingroup$ A* is a generalization of Dijkstra + heuristics; the performance is similar in worst case. To me, the important question for your problem is "what kind of information can you store in between the instances that will make the next instance faster?" E.g. if I store the previous shortest path, I'll be able to quickly find out if it "failed", but there isn't an obvious way to compute the next shortest path. (Even if you store k shortest paths from the previous instance, I suspect this holds for any k.) $\endgroup$
    – Lucas Cook
    Apr 27, 2012 at 21:10
  • $\begingroup$ (My previous comment is talking mainly about worst-case solutions. Maybe you care about average case? Then there might be a heuristic that makes a good A* type of solution.) $\endgroup$
    – Lucas Cook
    Apr 27, 2012 at 21:12
10
$\begingroup$

Dynamic graph models have been studied intensively in distributed computing. For distributed algorithms, the computation is structured into rounds and the topology of graphs (=network) might undergo some changes from round to round, which are under control of an adversary. Moreover, every node of the graph runs an algorithm which can send a message to its (current!) neighbors. (This message is the input of the neighbors' algorithm in the next round.) What makes things interesting, is that a node does not "see" the entire graph but only its local neighborhood.

Problems that are considered in these settings are for example information spreading where every node in the graph initially holds a token and eventually you want that every node has seen every token. The goal is to design algorithms that achieve this in the smallest number of rounds, using the least number of messages. See [2] for a recent survey.

For the non-distributed setting, you might want to look at [1], which is an extension of the paper that you've mentioned.

[1] Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, Fabio Vandin: Algorithms on evolving graphs. ITCS 2012: 149-160

[2] Fabian Kuhn, Rotem Oshman: Dynamic networks: models and algorithms. SIGACT News 42(1): 82-96 (2011)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Don't those message passing algorithms have problems with (lack of) convergence? $\endgroup$
    – Raphael ♦
    Apr 27, 2012 at 7:10
  • $\begingroup$ Not sure I understand what you mean with "convergence". As long as the graph remains connected in every round, the number of nodes that have seen a specific token t will increase by at least 1. Thus after n rounds everyone will have seen t, no matter how the adversary changes the topology. $\endgroup$
    – Peter
    Apr 27, 2012 at 8:34
  • $\begingroup$ I was thinking of the count-to-infinity problem caused by changing topology. $\endgroup$
    – Raphael ♦
    Apr 27, 2012 at 9:03
  • $\begingroup$ @Raphael In distributed dynamics, researchers are usually investigating with what properties can be worst case guaranteed within a certain time frame. Thus "convergence" cannot be guaranteed for distance-vector / Bellman-Ford because of fundamental problems with the technique in a dynamic environment. There are other convergent routing protocols that don't have the count-to-infinity problem. $\endgroup$
    – Lucas Cook
    Apr 27, 2012 at 9:50
3
$\begingroup$

Building on @Peter answers (it is a very long comment, so I just included as an answer hopping that someone will benefit from it).

I would suggest the following reference:

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: Time-varying graphs and dynamic networks. IJPEDS 27(5): 387-408 (2012)

The survey includes a theoretical classification of dynamic networks in distributed settings. For instance, you may find graphs in which the appearance of edges follows a periodic pattern. Or, edges show up at least once in a period $\Delta$. Or, edges that do not follow any periodic patter but they will show up at some point of the algorithm execution. -- and there are about 9 classes in total.

What is really important of this classification is that there are inclusion relationships between the different classes. So if you solve a problem in a certain class, you would solve it in every other class it is included in.

The same authors presented broadcasting algorithms on some of the mentioned graphs. They gave different performance metrics related to time (i.e. different definition of shortest time). In broadcasting, the idea is that each node build a view of the network in the time domain. This is done by repeatedly listening to neighbors, and sending information to neighbors. If assuming periodicity, then a node can tell what is the shortest time-path to another node. It uses this information in routing. More details can be found in:

Arnaud Casteigts, Paola Flocchini, Bernard Mans, Nicola Santoro: Deterministic Computations in Time-Varying Graphs: Broadcasting under Unstructured Mobility. IFIP TCS 2010: 111-124

One of the interesting concepts in dynamic graphs is the concept of journey, which has an analogy to path in static graphs. There is a journey between two nodes $u$ and $v$ if there is a set of edges $\{(u,x_1), (x_1, x _2), ...., (x _k, v)\}$ that will appear in an increasing intervals of time. Note that journey are not symmetric. The existence of a journey between $u$ and $v$ does not necessarily mean that there is a journey between $v$ and $u$.

I attended a lecture by the previous authors. From my understanding, they claim that we are far from being able to deal with dynamic graph algorithms (following the definitions they follow). That we are still in the case of simple classes. In fact, they claim that most of the mobile computing algorithms just assume that their algorithms are too fast to be executed while the network is in transition ! (which i believe I heard a lot) -- Or simply, assume periodicity of edges appearance (see delay tolerant networks etc)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.