0
$\begingroup$

Given a digraph $G = (V, E)$ and a set of vertices $S$, which does not change over the whole process, the goal is to compute the set of vertices, $R_{reach}$, reachable from $S$ and the set of nodes , $R_{ret}$, from which I can return to $S$.

The issue I have now, is that I need to add and remove edges. I can keep track of the changes in the graph. Note that these changes to the graph only happen locally, i.e. within a given range/distance around a vertex I know.

I have successfully been localizing the update of $R_{reach}$ and $R_{ret}$ for the edges I add to the graph. However, when I remove an edge from the graph one issue arises, that this edge might cut off a subgraph in term of reachability/returnability. I am not sure if it is possible to keep the update of $R_{reach}$ and $R_{ret}$ still local around the known vertex and the given update distance or if it is faster to simply recompute $R_{reach}$ and $R_{ret}$ for the whole graph again using BFS.

$\endgroup$
1
$\begingroup$

You can check the Dynamic Transitive Closure Problem of a Digraph. The transitive closure (or reachability) problem in a digraph $G=(V,E)$ consists in finding whether there is a directed path between any two vertices in $G=(V,E)$. The general idea is to maintain some kind of structure in order to quickly respond to queries of the form:

is there a path connecting u and v? Now add/delete an edge $e \in E$: is there a path connecting u and v?

Some algorithms respond in $O(1)$ time but need $O(n^2)$ space. Some respond yes/no and some also give you an actual path though I do not remember the exact complexity to get the path.

For your case you have to check all nodes of $S$ against all other nodes $V-S$.

The easiest way to do it is to run BFS every time for every node in $S$. It depends on the application.

Take a look in the bibliography below:

  • D. Yellin, Speeding up dynamic transitive closure, Acta Informatica 30 (1993), pp.369-384.
  • [I86] G. Italiano, Amortized Efficiency of a Path Retrieval Data Structure, Theoretical Computer Science, 48 (1986), pp. 273-281.
  • [I88] G. Italiano, Finding Paths and Deleting Edges in Directed Acyclic Graphs, Information Processing Letters, 28 (1988), pp. 5-11.

Hope this helps!

$\endgroup$
  • $\begingroup$ Thank you! This lead me to the following paper: "A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time" $\endgroup$ – nemo Jun 23 '16 at 13:06
  • $\begingroup$ No problem! Glad I could help! $\endgroup$ – Dimitris Jun 24 '16 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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